Compressed Sensing with Cross Validation

Rachel Ward

Source-linked AI summary

Compressed Sensing with Cross Validation

Rachel Ward

arXiv:0803.1845v2Mar 12, 2008math.NA

TL;DR

Compressed sensing estimates lack assured accuracy when the signal’s sparsity or compressibility is unknown. The paper uses cross validation to bound errors and select estimates or regularization parameters, showing tight bounds and favorable comparisons with OMP while identifying limits for entire solution paths and noisy settings.

Problem
When sparsity, compressibility, or the appropriate LASSO regularization parameter is unknown, the accuracy of a compressed sensing estimate cannot be directly evaluated.
Method
The paper applies cross validation and the Johnson–Lindenstrauss lemma to candidate estimates or solution-path points, using reserved measurements to approximate unknown errors and select among them.
Results
Cross validation provides tight numerical upper and lower error bounds, selects estimates whose error is within a small multiplicative factor of the best possible error, and can outperform or match OMP in reported settings.
Takeaways & Limitations
Reserving a small measurement subset enables practical error assessment and adaptive estimate selection, with larger gains when the assumed sparsity substantially exceeds the true sparsity.
Takeaways & Limitations
Applying the theory to an entire generic LASSO solution path may require O(N) cross-validation rows, which defeats the compressed sensing purpose; noisy-measurement extensions still require theoretical justification.

Abstract

from arXiv · show

Compressed Sensing decoding algorithms can efficiently recover an N dimensional real-valued vector x to within a factor of its best k-term approximation by taking m = 2klog(N/k) measurements y = Phi x. If the sparsity or approximate sparsity level of x were known, then this theoretical guarantee would imply quality assurance of the resulting compressed sensing estimate. However, because the underlying sparsity of the signal x is unknown, the quality of a compressed sensing estimate x* using m measurements is not assured. Nevertheless, we demonstrate that sharp bounds on the error || x - x* ||_2 can be achieved with almost no effort. More precisely, we assume that a maximum number of measurements m is pre-imposed; we reserve 4log(p) of the original m measurements and compute a sequence of possible estimates (x_j)_{j=1}^p to x from the m - 4log(p) remaining measurements; the errors ||x - x*_j ||_2 for j = 1, ..., p can then be bounded with high probability. As a consequence, numerical upper and lower bounds on the error between x and the best k-term approximation to x can be estimated for p values of k with almost no cost. Our observation has applications outside of compressed sensing as well.

1 Introduction

Compressed sensing recovers sparse or approximately sparse vectors from fewer linear measurements, but unknown sparsity makes estimate quality difficult to certify. The paper uses reserved measurements and cross validation to assess multiple candidate reconstructions and estimate approximation error.

1 Introduction: Compressed sensing reconstructs sparse or approximately sparse N-dimensional vectors from m<N linear measurements using matrices and recovery algorithms designed for sparse signals.The measurement vector is y=Φx, and recovery guarantees rely on structural assumptions such as sparsity and the Restricted Isometry Property.
1 Introduction: Unknown sparsity prevents a general quality guarantee for compressed sensing estimates because the relevant approximation level k depends on the signal and measurement budget.The theoretical error bound depends on how well x is approximated by a k-sparse vector, but real-world signals may not have a known sparsity level.
1 Introduction: Reserved measurements and the Johnson-Lindenstrauss lemma turn residual measurements into proxies for the unknown errors of up to p candidate estimates.The implementation measurements generate candidate reconstructions, while independent cross-validation measurements estimate their errors with high probability.
1 Introduction: The procedure provides tight numerical upper and lower error bounds for up to p compressed sensing estimates and estimates best k-term approximation errors for up to p values of k.It also selects a candidate by minimizing its cross-validation residual, with error within a small multiplicative factor of the best candidate in the sequence.
1 Introduction: Cross validation reserves r measurements as a test set after the remaining m−r measurements produce a sequence of candidate approximations.The candidate sequence can vary algorithm parameters such as m, k, or γ, depending on the decoder.

2 Preliminary Notation

The paper introduces notation for sparse approximation and a one-sided multiplicative relation used to compare positive quantities and sequences.

2 Preliminary Notation: The notation indicates that a vector x∈R^N has exactly n nonzero coefficients.
2 Preliminary Notation: The relation a∼_εb means that a approximates b within a multiplicative factor of 1±ε, and the relation is not symmetric.
2 Preliminary Notation: The multiplicative relation is preserved for ratios under a transformed parameter and for minima taken across two pointwise-comparable sequences.For ratios, the transformed parameter is δ=2ε/(1−ε); for sequence minima, the same ε is retained.

3 Mathematical Foundations

The mathematical foundation is the Johnson-Lindenstrauss embedding, which preserves distances among finitely many points using a random low-dimensional projection with high probability.

3 Mathematical Foundations: The Johnson-Lindenstrauss lemma embeds p points into O(ε^-2 log p) dimensions while distorting pairwise Euclidean distances by at most a factor of 1±ε.The paper notes that Gaussian and other random matrix constructions can provide such embeddings.
3 Mathematical Foundations: A random matrix with independent entries, variance 1/r, and suitable concentration properties preserves the norm of a fixed vector with probability exceeding 1−δ.For Gaussian and Bernoulli constructions, the constant controlling the required number of rows can be taken as C=8.
3 Mathematical Foundations: The expected squared norm of a random projection equals the original squared norm, while concentration controls deviations from this expectation.
3 Mathematical Foundations: Applying the fixed-vector concentration bound to p predetermined points and using a union bound yields simultaneous guarantees with failure probability at most ξ=pδ.Setting δ=ξ/p gives a target confidence level for all p points.

4 Cross Validation in Compressed Sensing

The method splits measurements into an implementation matrix for generating candidate estimates and an independent cross-validation matrix for selecting among them and estimating their errors. With r = O(log p) additional measurements, the procedure provides high-probability error bounds, subject to correct normalization and independence.

The implementation measurements generate candidate estimates while reserved, independent cross-validation measurements select one estimate and estimate its error.Candidates may correspond to increasing values of an input parameter such as m, k, or γ.
r = ⌈Cϵ^-2 log pξ^-1⌉ cross-validation rows suffice to bound the errors of p estimates with probability at least 1−ξ.The cross-validation matrix is Gaussian or Bernoulli, normalized according to Lemma (3.2), and independent of the estimates.
The same bounds can estimate the unknown oracle error associated with the best approximation in the relevant ℓ_2 metric.This follows by including x itself alongside the candidate error vectors in the embedding argument.
The observable cross-validation residual ||Ψ(x−x̂_j)||_r functions as a proxy for the unknown reconstruction error ||x−x̂_j||_2.The theorem derives bounds by applying the embedding lemma to the error vectors and rearranging the resulting inequalities.
Independence between Ψ and the implementation measurements is crucial, and normalization is essential when estimating unnormalized errors.Normalization is less important for normalized errors or when only the minimizer is needed, but must account for the number of cross-validation rows r for ||x−x̂_j||_2.

5 Applications of cross validation to compressed sensing

Cross validation selects among compressed sensing estimates and bounds their unknown approximation errors, extending from best k-term estimation to adaptive measurement, sparsity, and regularization choices.

5.1 Estimation of the best k-term approximation error: Cross validation can obtain tight upper and lower bounds on the unknown k-sparse approximation error with almost no effort.
5.1 Estimation of the best k-term approximation error: Reserving roughly 10 log p measurements allows estimation of errors across p candidate sparsity levels.
5.2 Choice of the number of measurements m: Adaptive decoding partitions measurements between an implementation matrix that generates candidate estimates and cross validation matrices that estimate their errors.
5.2 Choice of the number of measurements m: The adaptive procedure increases measurement levels until a cross-validated normalized error falls below a threshold, or warns when the reconstruction remains untrustworthy.
5.3 Choice of regularization parameter in homotopy-type algorithms: For homotopy-type methods, cross validation selects a regularization value from solution-path kinks and yields an error within a small multiplicative factor of the best sampled error.
5.3 Choice of regularization parameter in homotopy-type algorithms: Evaluating an entire generic LASSO path is not provably efficient because its number of kinks can be very large, although random compressed sensing matrices suggest an O(log m) heuristic.

6 Orthogonal Matching Pursuit: A case study

The OMP case study applies cross-validation when the signal sparsity is unknown, using held-out measurements to select among OMP iterates and estimate reconstruction error. Experiments show that OMP-CV closely tracks oracle and residual errors, with performance depending on the measurement split and sparsity gap.

6.1 Experimental setup: OMP-CV selects among OMP iterates when the true sparsity d is unknown and k is only an upper bound.Each OMP iterate represents a hypothesis about the number of significant coordinates, making cross-validation applicable to the sequence of estimates.
6.1 Experimental setup: The experiment reserves r of m = 800 measurements for cross-validation and uses n = m − r measurements to generate the OMP estimate sequence.A Gaussian n × N matrix produces the OMP iterates, while independent r × N matrices evaluate their cross-validation errors.
6.2 Experimental Results: The error bound tightens as r increases, but larger r leaves fewer training measurements, so r = 30 is suggested as a practical balance in Figure 1.The figure varies r from 5 to 90 and reports better approximation of residual error by OMP-CV than OMP, even with few validation measurements.
6.2 Experimental Results: OMP-CV errors provide a proxy for the oracle error and can upper-bound the unknown residual error, while the theoretical concentration bound is tight in Figure 1.The cross-validation quantities are observable, unlike the oracle, OMP, and residual errors.
6.2 Experimental Results: With high probability, OMP-CV using r = 15 improves on OMP, while r = 30 yields an overwhelming-probability improvement and corresponds to the heuristic ϵ ≤ .6.The reported accuracy parameters are ϵ(15) = .8405 and ϵ(30) = .5943.
6.2 Experimental Results: OMP-CV improves more when d is far below k; when d is close to k, it may not improve accuracy but is guaranteed not to underperform OMP.The experiment uses d = 100 and k = 200, creating a substantial sparsity gap.

7 Beyond Compressed Sensing

The cross-validation analysis extends beyond compressed sensing to underdetermined linear inverse problems with iterative decoding. It can bound errors across successive approximations and select an earlier iterate when later iterations introduce overfitting artifacts.

7 Beyond Compressed Sensing: For an underdetermined inverse problem y = Ax with decoder Δ, cross-validation can evaluate a sequence of successive approximations.The framework applies when A is known and sparsity may be imposed on x.
7 Beyond Compressed Sensing: Cross-validation can select an earlier approximation when later iterations introduce parameter-overfitting artifacts.The selected estimate comes from the entire sequence rather than necessarily being the final iterate.

8 Extensions and Open Problems

The paper presents measurement holdout as a low-cost way to select estimates and bound approximation error, while identifying open questions about validation schemes, noisy measurements, and alternative metrics. It also notes empirical evidence that the technique may apply to broader measurement ensembles.

8 Extensions and Open Problems: Reserving r measurements lets cross-validation choose the best approximation from p decoding estimates and estimate error to the best k-sparse approximation.The required validation budget is generally r = O(log(p)) measurements.
8 Extensions and Open Problems: The analysis is specifically based on holdout cross-validation, leaving the use of K-fold cross-validation as an unresolved extension.The discussion considers partitioning measurements into training and validation subsets.
8 Extensions and Open Problems: Theorem (4.1) has no clear extension to the noisy compressed sensing model, although prior experiments suggest cross-validation can work there.The noisy model includes Gaussian measurement noise and quantization error, but theoretical justification remains open.
8 Extensions and Open Problems: The paper studies cross-validation only in the ℓ2 metric, while applicability to ℓ1 and other reconstruction metrics remains unresolved.The authors note that no ℓ1 analogue of the Johnson–Lindenstrauss lemma is available for their theorem.
8 Extensions and Open Problems: Random Fourier measurement matrices empirically show concentration behavior similar to Gaussian and Bernoulli matrices, suggesting broader cross-validation applicability.The theoretical justification for these ensembles remains an open problem.