TL;DR
This paper introduces a novel multiscale iterative algorithm for reconstructing signals from their wavelet transform magnitudes (scalograms). By reformulating the phase retrieval problem using the holomorphic extension of the wavelet transform, the algorithm efficiently propagates phase information from low to high frequencies, achieving precise and stable reconstructions, even for large signals.
What Problem Does This Paper Address?
The paper tackles the challenging problem of phase retrieval from the scalogram of a signal. The scalogram, which is the modulus of the wavelet transform, is widely used in audio processing and other fields. However, it discards the phase information, which is crucial for perfectly reconstructing the original signal. Reconstructing a signal from its scalogram is an inverse problem that is known to be difficult due to the non-convex nature of the problem, often leading to solutions stuck in local minima. While existing methods like iterative projections (e.g., Griffin-Lim) and convexification techniques exist, they either struggle with local minima, have high computational complexity, or are not guaranteed to work for non-random measurements like those from wavelet transforms. This paper aims to provide a precise, stable, and computationally efficient solution for this problem, particularly for large signals.
Methods
The core of the proposed solution lies in a new reformulation of the phase retrieval problem. This reformulation leverages the holomorphic extension of the wavelet transform. By introducing two auxiliary wavelet families, the authors transform the problem into a form that allows for a multiscale iterative reconstruction.
Here's a breakdown of the key methodological aspects:
- Reformulation via Holomorphic Extension: The authors introduce auxiliary wavelet families,
ψ_lowandψ_high, which are related to the original waveletψ_j. This allows them to express the phase retrieval condition in a new form involving these auxiliary wavelets. This reformulation is key to enabling the multiscale approach. - Multiscale Reconstruction: The algorithm reconstructs the signal scale by scale, starting from low frequencies and progressing to high frequencies. This is facilitated by the reformulated problem, which allows phase information to be propagated from lower scales to higher ones.
- Local Optimization: A natural objective function is derived from the reformulated problem. While non-convex, it is observed to have fewer local minima than traditional objective functions, making it amenable to local optimization techniques (specifically, L-BFGS is used in the implementation).
- Phase Propagation: The multiscale nature allows for a stable deconvolution step to estimate the signal's components at higher frequencies, leveraging the already reconstructed lower-frequency components.
- Error Correction: A multigrid error correction step is introduced to mitigate errors that can arise during the phase propagation, especially when dealing with noisy data.
- Exhaustive Search Initialization: For very small problems, an exhaustive search method is used to find all possible solutions. This is crucial for initializing the multiscale reconstruction process.
Datasets
The paper evaluates its algorithm on several types of synthetic and real-world signals:
- Realizations of Gaussian random processes: Used to test the algorithm's performance on signals with a relatively uniform distribution of wavelet transform magnitudes.
- Lines from images: Signals extracted from photographs, characterized by oscillating parts and smooth regions.
- Sums of a few sinusoids: Signals with potentially small wavelet transform components, posing a greater challenge.
- Audio signals: Real-world audio recordings, including musical pieces ("Flight of the Bumblebee") and speech ("I'm sorry"). These are noted as particularly challenging due to the absence of very low frequencies and the presence of many small wavelet coefficients.
No new datasets were introduced; the focus was on evaluating the algorithm's performance on existing signal types.
Key Insights and Ideas
- The power of reformulation: The core insight is that reformulating the phase retrieval problem using the holomorphic extension of the wavelet transform unlocks a multiscale approach that was not possible with the classical formulation. This reformulation is the key enabler for efficient phase propagation.
- Multiscale is better: The paper strongly advocates for multiscale approaches in phase retrieval. They argue that this strategy helps overcome potential ill-conditioning of the problem and makes iterative algorithms less sensitive to initialization, leading to better convergence and reconstruction quality.
- Local stability is key: The authors highlight that phase retrieval is not uniformly stable. While the modulus of the wavelet transform might be well-reconstructed, the signal itself might differ significantly. This "local stability" property, where the reconstructed signal's scalogram is close to the original, is a crucial aspect of their findings.
- Small values are the enemy: The presence of many small values in the wavelet transform, especially at low frequencies, is identified as the primary source of difficulty for the algorithm and for phase retrieval in general. This is because it makes the deconvolution steps unstable.
Key Results
- Precise and stable reconstruction: The algorithm achieves precise and stable reconstructions across various signal types, including audio.
- Linear complexity: The algorithm's complexity is linear in the signal size (up to logarithmic factors), making it applicable to large signals, which is a significant advantage over some existing methods.
- Superiority over non-multiscale methods: Numerical results show that the multiscale approach significantly outperforms non-multiscale methods like the classical Gerchberg-Saxton algorithm, yielding a mean error approximately twice as small.
- Competitive with state-of-the-art: The algorithm's precision is comparable to methods like PhaseLift, but it offers a substantial speedup, allowing for the reconstruction of larger signals.
- Error reduction with correction: The error correction step is shown to significantly reduce reconstruction errors, especially when local optimization steps are limited.
- Impact of wavelet choice: The choice of wavelets significantly impacts performance, with Morlet wavelets showing good results due to their fast decay and good overlap.
Limitations and Future Work
- Sensitivity to small values: The algorithm's performance degrades when the wavelet transform has many small values, particularly in the low frequencies, due to unstable deconvolution steps. This is identified as an intrinsic difficulty of the phase retrieval problem itself, rather than an artifact of the algorithm.
- Failure cases: For challenging signals (like sums of sinusoids and audio), the algorithm can still fail with a small probability, although less frequently than PhaseLift. In these failure cases, the error on the signal can be significantly larger than the error on the modulus.
- Future Work: The authors plan to investigate further ways to speed up the reconstruction, including parallelization. They also aim to test the algorithm on concrete applications like source separation.
Summary updated