Abstract
The theory behind compressive sampling pre-supposes that a given sequence of observations may be exactly represented by a linear combination of a small number of basis vectors. In practice, however, even small deviations from an exact signal model can result in dramatic increases in estimation error; this is the so-called “basis mismatch” problem. This work provides one possible solution to this problem in the form of an iterative, biconvex search algorithm. The approach uses standard $\ell_1$-minimization to find the signal model coefficients followed by a maximum likelihood estimate of the signal model. The algorithm is illustrated on harmonic signals of varying sparsity and outperforms the current state-of-the-art.
Introduction
Compressive Sensing (CS) has revolutionized signal processing by enabling the reconstruction of high-resolution signals from sub-Nyquist measurements. This success hinges on the assumption that the signal is sparse in a known basis, such as the Fourier basis. However, a significant hurdle remains: the "basis mismatch" problem. In real-world scenarios, signal frequencies rarely align perfectly with a predefined mathematical grid. When a frequency falls between grid points, the signal's energy "leaks" across the spectrum, destroying sparsity and causing standard recovery algorithms to fail.
The Alternating Convex Search (ACS) Algorithm
To address this, we propose the Alternating Convex Search (ACS) algorithm. Rather than relying on a fixed frequency grid, ACS treats frequency locations as variables to be optimized iteratively.
The algorithm consists of two primary stages:
- Coefficient Estimation: With the frequency grid fixed, the algorithm employs $\ell_1$-minimization (specifically the Gradient Projections for Sparse Reconstruction, or GPSR) to identify the sparsest coefficients that fit the data.
- Frequency Refinement: With the coefficients fixed, a Maximum Likelihood (ML) estimate is used to "nudge" the frequency grid lines toward the actual signal components.
A key innovation is the decomposition of the multi-dimensional frequency search into $S$ independent one-dimensional searches, where $S$ is the number of harmonics. This makes the algorithm computationally efficient while maintaining robustness.
Biconvexity and Convergence
While the joint optimization of coefficients and frequencies is non-convex, the problem is "biconvex." This means that fixing one set of variables makes the problem convex with respect to the other. This property ensures that the alternating search converges monotonically toward a local minimum, providing a stable and reliable recovery path.
Experimental Evaluation
The ACS algorithm was tested using synthetic harmonic signals consisting of complex sinusoids. Experiments typically used a signal length of $N=256$ with $M=128$ compressed observations. Gaussian noise was added to achieve a Signal-to-Noise Ratio (SNR) of 40dB. ACS was compared against standard GPSR, Overcomplete Fourier Dictionaries (OC-GPSR), Semi-Definite Programming (SDP), and the Greedy Forward-Backward (GFB) algorithm.
Results and Discussion
ACS demonstrates a superior balance between accuracy and computational speed. While Semi-Definite Programming (SDP) offers high accuracy, it is computationally intensive, often taking minutes per simulation. In contrast, ACS achieves comparable accuracy in mere seconds.
As shown in the figure above, standard GPSR (blue circles) suffers from significant energy leakage, producing many non-zero coefficients around the true frequencies. ACS (red crosses) successfully refines the grid to match the true frequency locations (dashed lines) and coefficient values (diamonds), resulting in a much sparser and more accurate model. Unlike overcomplete dictionary methods, which often lead to overfitting, ACS adapts the basis to the signal itself.
Conclusion
The Alternating Convex Search algorithm provides a robust solution to the basis mismatch problem in harmonic signal recovery. By leveraging biconvexity, it offers a computationally efficient alternative to heavy-duty optimization methods like SDP. Future work will explore extending this framework to more general dictionaries and establishing broader theoretical convergence bounds in high-noise environments.
Summary updated