Robust Spectral Compressed Sensing via Structured Matrix Completion

Yuxin Chen; Yuejie Chi

Source-linked AI summary

Robust Spectral Compressed Sensing via Structured Matrix Completion

Yuxin Chen, Yuejie Chi

arXiv:1304.8126v5Apr 30, 2013cs.ITeess.SYmath.NAstat.ML

TL;DR

Spectral compressed sensing is posed as structured low-rank matrix completion to recover spectrally sparse signals without prior model-order knowledge or basis mismatch. EMaC uses an enhanced Hankel form and nuclear-norm recovery, achieving exact or stable recovery under mild incoherence conditions, while remaining applicable to arbitrary outliers and super resolution.

Problem
Naive matrix completion can require far more than the Θ(r) degrees of freedom and may produce full-rank enhanced matrices, motivating forms that better capture harmonic structure.
Method
EMaC arranges partial time-domain data into a two-fold Hankel enhanced matrix and recovers it through nuclear-norm minimization without requiring prior model-order knowledge.
Results
Under mild incoherence conditions, EMaC enables exact recovery from O(r log^4 n) random samples and remains stable against bounded noise and a constant portion of arbitrary corruptions.
Takeaways & Limitations
The method recovers multi-dimensional unknown frequencies with infinite precision, addresses basis mismatch, and has been extended numerically to super resolution.
Takeaways & Limitations
Performance guarantees for super resolution comparable to prior work remain open, and more efficient numerical solvers are needed for large datasets.

Abstract

from arXiv · show

The paper explores the problem of \emph{spectral compressed sensing}, which aims to recover a spectrally sparse signal from a small random subset of its $n$ time domain samples. The signal of interest is assumed to be a superposition of $r$ multi-dimensional complex sinusoids, while the underlying frequencies can assume any \emph{continuous} values in the normalized frequency domain. Conventional compressed sensing paradigms suffer from the basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this issue, we develop a novel algorithm, called \emph{Enhanced Matrix Completion (EMaC)}, based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multi-fold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of $r\log^{4}n$, and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC still allows exact recovery, provided that the sample complexity exceeds the order of $r^{2}\log^{3}n$. Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multi-fold Hankel or Toeplitz matrix from minimal observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments.

I. INTRODUCTION

The paper studies recovery of multidimensional spectrally sparse signals from few random time-domain samples when frequencies are continuous, avoiding discrete-grid basis mismatch. EMaC converts harmonic structure into low rank through structured matrix completion and provides recovery guarantees under incoherence conditions.

Motivation: Spectral compressed sensing recovers a signal formed by r multidimensional complex sinusoids at arbitrary continuous frequencies from few random time-domain samples.The model uses normalized frequencies in the unit interval.
Motivation: Discrete-domain compressed sensing can avoid prior model-order knowledge but suffers basis mismatch when frequencies do not lie on the imposed grid.Prior remedies for basis mismatch generally lack theoretical guarantees in the cited setting.
Method: EMaC arranges samples into a low-rank enhanced matrix with K-fold Hankel structure and completes it by nuclear norm minimization without imposing a frequency grid.The enhanced rank is bounded by the spectral sparsity r, while corrupted observations are handled with weighted nuclear norm and ℓ1 minimization.
Guarantees: O(r log^4 n) random samples suffice for exact recovery under mild incoherence, and O(r^2 log^3 n) suffice with a constant proportion of arbitrary corruptions.The method is also stable against bounded noise, and the incoherence condition depends on frequency locations rather than coefficient amplitudes.
Contributions: The paper provides theoretical guarantees for low-rank Hankel and Toeplitz matrix completion that are close to the information-theoretic limit.The authors state these guarantees have applications in control, natural language processing, and computer vision.
Contributions: The work extends prior results by removing an additional strong incoherence condition that lacked physical interpretation and improving sample complexity.The paper also discusses numerical validation and applicability to super resolution.

C. The EMaC Algorithm in the Absence of Noise

EMaC completes an enhanced matrix that captures multi-fold Hankel structure by minimizing its nuclear norm subject to observed samples. Its recovery depends on incoherence and on choosing pencil parameters that keep the enhanced matrix relatively square.

Algorithm: EMaC minimizes the nuclear norm of an enhanced form over all matrices compatible with the observed samples.The enhanced form exhibits the harmonic structure needed for structured matrix completion.
Parameter choice: The required sample complexity increases with cs, so theory and experiments favor pencil parameters that make the enhanced matrix close to square.The recommended scaling takes both k_i and n_i − k_i + 1 proportional to n_i.
Incoherence: The incoherence condition depends only on frequency locations and is satisfied when the associated Gram matrices are well conditioned.The measure is characterized by the reciprocal of the smallest singular value of Gram matrices formed from Dirichlet-kernel evaluations.
Incoherence: For randomly located frequencies, the minimum eigenvalue of GL approaches one as the enhancement parameter k grows.The empirical distributions for k = 6, 36, and 72 support the stated trend.
Incoherence: For small off-grid perturbations, the least singular values of GL and GR are lower bounded by 3/4.This follows from bounding all off-diagonal entries by 1/(4r).

B. Theoretical Guarantees

Theoretical guarantees establish exact, stable, and robust recovery under incoherence, while extending the framework to higher-dimensional and general Hankel or Toeplitz completion.

Exact recovery from noiseless measurements: Under incoherence, noiseless EMaC uniquely recovers the enhanced matrix from m > c1µ1csr log4(n1n2) random samples with high probability.The guarantee applies to deterministic data and depends on frequency locations rather than sinusoid amplitudes.
Exact recovery from noiseless measurements: O(r log4(n1n2)) samples suffice for perfect recovery when µ1 is a small constant, which is orderwise optimal up to a logarithmic gap.The signal has Θ(r) degrees of freedom, while the logarithmic factor may be refined through sharper concentration inequalities.
Robust recovery in the presence of sparse outliers: Robust-EMaC exactly separates the signal from sparse corruptions affecting a constant portion of samples, under incoherence and τ ≤ 0.1.The regularization parameter can be chosen from the observation-set size, although cross-validation may work better in practice.
Extensions to structured matrix completion: The framework extends to K-dimensional signals through K-fold Hankel matrices and to general two-fold Hankel completion, with analogous guarantees for Toeplitz completion.For K-dimensional models, the enhanced matrix has rank at most r; Theorem 4 transfers the main bounds to two-fold Hankel matrices under a weaker incoherence condition.

A. Phase Transition in the Noiseless Setting

Numerical experiments show that EMaC’s noiseless recovery threshold scales approximately linearly with spectral sparsity and remains effective for continuous, closely spaced frequencies. Additional experiments demonstrate stability under noise, robustness to outliers, and applicability to super resolution.

Noiseless phase transition: The number of samples m grows approximately linearly with spectral sparsity r in 11 × 11 and 15 × 15 phase-transition experiments.The phase-transition slopes were approximately the same for both matrix dimensions.
Noiseless phase transition: The reconstructed NMSE grows approximately linearly with δ for r = 4, n1 = n2 = 11, and m = 50.This experiment used a noise-free dataset to assess Noisy-EMaC’s stability parameter dependence.
Comparison with existing approaches: EMaC retains a sharp phase transition without frequency separation, whereas the atomic norm approach degenerates severely when separation is absent.With separation imposed, the atomic norm phase transition greatly improves, while EMaC shows similar performance and is less sensitive to separation.
Robust recovery: With 10% of entries corrupted, the robust method still shows an approximately linear tradeoff between measurements m and recoverable sparsity r.When all entries are observed, the experiments also show a large region of exact recovery across sparsity and outlier levels.
Super resolution: EMaC greatly enhances resolution by extrapolating high-frequency components from low-frequency observations, although theoretical super-resolution guarantees are left for future work.The synthetic example used fhi/flo = 2 and reconstructed the signal through inverse Fourier transform.

C. Construction of Dual Certificates

The proof constructs a dual certificate through a golfing scheme and bounds its tangent and orthogonal components under incoherence and random sampling. These bounds establish exact and unique recovery once the sample size scales polylogarithmically with the enhanced matrix dimensions.

Certificate construction: The dual certificate W is constructed by initializing F_0 and recursively applying projections over independent random sample multisets.The golfing scheme uses j_0 iterations and sampling with replacement.
Norm bounds: The analysis controls three norms to bound the orthogonal component ∥P_T⊥(W)∥.The proof introduces auxiliary norms and lemmas relating ∥·∥, ∥·∥_{A,2}, and ∥·∥_{A,∞}.
Sample complexity: m > c̃_7µ_1c_s r log^4(n_1n_2) suffices for the required dual-certificate bounds under the stated hypotheses.This condition follows from the preceding bounds involving µ_1, c_s, and logarithmic factors.
Recovery guarantee: With high probability, W satisfies the dual-certificate conditions, so EMaC has an exact and unique solution.The conclusion follows by applying the dual-certificate lemma after verifying the required conditions.

VII. PROOF OF THEOREM 3

This section proves robust recovery by extending the dual-certificate argument to a low-rank signal plus structured sparse corruption model. The proof uses clean and corrupted sampling sets, random-sign analysis, and separate bounds for the low-rank and sparse components.

Robust formulation: Robust-EMaC imposes multi-fold Hankel structure on both the low-rank signal matrix and the sparse corruption matrix.Its proof follows robust principal component analysis through duality and a golfing-scheme certificate.
Sampling model: The sampling model separates clean observations from corrupted entries, with the modified model preserving orderwise bounds while simplifying independence assumptions.The clean set contains a (1−τ) fraction of observations, while the remaining observed locations are treated as dirty.
Random-sign analysis: The random-sign theorem assumes incoherence for X and independently generated zero-mean signs for nonzero entries of S.The theorem uses a regularization parameter λ and provides the basis for the robust recovery result.
Recovery guarantee: Under the theorem’s conditions, Robust-EMaC recovers X with probability exceeding 1−(n_1n_2)^−2.The certificate conditions imply exact recovery of the low-rank component despite the structured sparse corruption.
Sample complexity: m > c_8µ_1^2c_s r^2 log^3(n_1n_2) is sufficient for the robust dual-certificate bounds.The proof combines bounds on tangent-space contraction, sparse-sign projections, and orthogonal components.

VIII. CONCLUDING REMARKS

The paper presents EMaC as an efficient low-rank Hankel matrix completion method for continuous-frequency spectral compressed sensing. It reports infinite-precision frequency recovery under incoherence, robustness to noise and corruptions, and numerical applicability to super resolution, while identifying unresolved guarantees and scalability challenges.

Contribution: EMaC estimates spectrally sparse signals from partial time-domain samples without prior knowledge of the model order.It formulates spectral compressed sensing as low-rank Hankel structured matrix completion.
Guarantees: Under mild incoherence conditions, EMaC recovers multi-dimensional unknown frequencies with infinite precision, avoiding basis mismatch.The paper also reports stability to bounded noise and a constant proportion of arbitrary corruptions.
Applications: Numerical experiments extend the method’s demonstrated applicability to super resolution.The conclusion distinguishes this numerical extension from the paper’s theoretical recovery guarantees.
Limitations and open problems: The paper leaves performance guarantees for super resolution unresolved and notes the need for efficient large-dataset solvers.These are stated as open directions in the concluding remarks.

APPENDIX A BERNSTEIN INEQUALITY

The appendix develops concentration and norm arguments used to establish EMaC’s optimality and uniqueness. The proof constructs suitable nuclear-norm subgradients and shows that any feasible nonzero perturbation increases the objective.

Concentration tool: Bernstein’s inequality provides high-probability bounds for sums of independent, mean-zero random matrices with bounded operator norm.The stated version applies to matrices of dimension d_1×d_2 and gives failure probabilities controlled by d_1+d_2.
Optimality proof: A valid dual certificate and the constraint P_Ω(X+H)=P_Ω(X) are used to compare the nuclear norms of the true enhanced matrix and a perturbed candidate.The argument decomposes the perturbation into tangent-space and orthogonal components.
Uniqueness proof: If the orthogonal perturbation component vanishes, the projection conditions force H_e=0, proving uniqueness of the minimizer.The proof treats the complementary case separately and again concludes that the perturbation must be zero.
Structured bounds: The multi-fold Hankel structure and incoherence bounds control inner products involving structured sampling matrices.These estimates support the technical norm inequalities used in the recovery proof.

APPENDIX D PROOF OF LEMMA 3

The proof bounds random sampling operators and applies Bernstein’s inequality to establish the required high-probability control under a logarithmic sample condition.

m > c1µ1csr log (n1n2) gives the stated high-probability bound from Lemma 11.The probability exceeds 1 − (n1n2)^−4.
The proof separately controls expected energies and operator norms of the sampled components before invoking Lemma 11.These bounds use the structure and diagonal support of the relevant operators.
Bernstein’s inequality combines the preceding operator-norm and variance bounds into a final concentration estimate.The resulting bound holds with high probability for an absolute constant c2 > 0.

APPENDIX F PROOF OF LEMMA 5

The proof controls structured matrix norms by decomposing matrices into four triangular block components and bounding each component over dyadic index subsets.

Incoherence bounds: The row energy of UV ∗ is bounded by the incoherence parameter, and PT is shown to have analogous structural properties.These properties reduce the target estimates to the general feasible-matrix bound.
Matrix decomposition: Matrices are split into four parts according to upper or lower triangular components within upper or lower triangular blocks.The four pieces separately cover all combinations of block and within-block triangular structure.
Matrix decomposition: The analysis bounds each component separately, then combines the four estimates to control the full structured norm.The argument explicitly demonstrates the first component and states that the others follow similarly.
Dyadic partitioning: The index set is partitioned into subsets Wi,j arranged by logarithmic row and column scales.Each subset is analyzed using its row support and energy allocation.
Dyadic partitioning: Combining the bounds over all Wi,j yields the desired norm estimate with high probability.The intermediate bounds use the RMS-AM inequality and the assumed per-row energy constraint.

APPENDIX I PROOF OF LEMMA 8

The proof establishes Robust-EMaC recovery by analyzing feasible perturbations and showing that the enhanced signal perturbation must vanish under the stated conditions.

Perturbation analysis: Any optimizer perturbation satisfies PΩ⊥(S + T ) = 0 and PΩ(T ) = T.These relations follow from the sparse component’s support and the optimization constraints.
Dual certificate: A dual matrix satisfying the certificate conditions makes the objective perturbation nonnegative, constraining any alternative optimizer.The argument combines the dual inequalities with optimality of (X + H, S + T ).
Perturbation analysis: The invertibility condition on PT AΩcleanPT is converted into a lower-bound relation used to rule out nonzero perturbations.The proof also uses A⊥(He) = 0 and ∥PT (M)∥F ≤ ∥M∥F.
Recovery conclusion: Robust-EMaC succeeds under Condition (109), because PT (He) = PT ⊥(He) = 0 implies He = 0.The enhanced perturbation He is the enhanced form of H.
Recovery conclusion: In the complementary case, the proof uses the argument from Lemma 1 with Ω replaced by Ωclean to conclude He = 0.This completes the perturbation analysis for the alternative case.

APPENDIX J PROOF OF LEMMA 9

The proof models corrupted-entry signs with independent random unit-amplitude variables, then uses concentration and collision bounds to control the resulting enhanced sparse component.

Random corruption model: The dirty-entry sign pattern is represented by independent zero-mean random phases or signs supported on Ωdirty.Real entries are ±1, while complex entries have unit amplitude and arbitrary phase.
Auxiliary construction: The proof introduces an auxiliary dirty multiset sampled independently with replacement and compares its enhanced matrix with the actual sign pattern.This auxiliary construction separates concentration analysis from duplicate-location effects.
Concentration bounds: The concentration argument bounds conditional means, variances, and individual random-variable magnitudes before applying Lemma 11.The variables are conditionally independent after conditioning on the relevant index set.
Concentration bounds: Bernstein’s inequality provides high-probability bounds once ρτn1n2 is sufficiently larger than log(n1n2).The stated probability exceeds 1 − (n1n2)^−4.
Collision control: Sampling collisions affect at most 10 log(n1n2) locations with high probability, enabling a bound on the discrepancy between auxiliary and actual matrices.The conflict count follows from a Chernoff bound.

APPENDIX K PROOF OF LEMMA 10

The appendix proves Lemma 10 under the conditions of Lemma 1 by controlling conditional deviations and perturbations of the enhanced matrix. The argument combines these bounds with Hankel structure and requires sufficiently large dimensions and sampling.

Concentration bounds: Conditioned on K, the auxiliary variables are conditionally independent, enabling concentration bounds for the deviation involving ˜Se and ρτKe.The proof applies Lemma 11 to obtain high-probability bounds.
Concentration bounds: The operator norm of ρτKe is bounded using the decomposition of Ke and a further application of Lemma 11.This bound is combined with the earlier deviation estimate through the constant c18 = max{c16, c17}.
Sampling requirement: The high-probability argument requires ρτn1n2 > 100 log(n1n2) / c18, with τ chosen sufficiently small.This condition follows from combining the concentration estimates and the stated sampling requirement.
Proof conditions: The proof assumes the conditions of Lemma 1, which were previously shown to hold with high probability.It also invokes sufficiently large n1 and n2.
Noisy-EMaC perturbation: For Noisy-EMaC, the proof decomposes He into observed and unobserved components and bounds their Frobenius or operator effects using triangle inequalities and Hankel structure.The argument treats separate cases for He and combines the resulting inequalities into the final bound.
Noisy-EMaC perturbation: The perturbation analysis concludes by combining the preceding inequalities, including the condition that AΩ⊥(He) can vanish in one case.The final result is stated as holding with high probability.