Motivation
An underdetermined matrix has a nonzero null vector, so arbitrary coefficients cannot be recovered uniquely from their measurements. Sparse recovery asks a narrower question: can two vectors with only a few nonzero entries produce the same data? Even when the answer is no, so sparse vectors are uniquely determined, a numerical reconstruction must still cope with noise. We will separate three statements: uniqueness among sparse vectors, stability when the correct support is already known, and bounds on correlations after projecting out selected columns. None by itself is a guarantee that an algorithm discovers the support.
Definitions
Definition 16.4.1
(Restricted isometry property)
Let , with columns . For , is its column submatrix, and counts nonzero entries. For , suppose there is a number such that every vector supported on at most indices satisfies
This is the restricted isometry property (RIP) of order with constant at most . More generally, denotes the smallest for which both inequalities hold for every such vector; this constant may be at least one, and order- RIP holds precisely when .
The hypothesis includes lower and upper bounds; unit column norms alone do not imply it. When , RIP with requires full column rank, whereas a wide matrix can still have RIP at a smaller order. Throughout, arithmetic is exact and vectors and matrices are real.
Concept lensAlgebraic
Restricted isometry as an eigenvalue condition on Gram submatrices
For supported on , with . Hence order- RIP with constant says exactly that every eigenvalue of every with lies in , that is,
Equivalently, every singular value of every such lies in . Sets with suffice: a smaller Gram matrix is a principal submatrix of a larger one, and eigenvalue interlacing keeps its eigenvalues inside the larger range. The worked examples compute in exactly this way.
Theorem/proposition
Theorem 16.4.2
(Uniqueness and noise stability)
Let be an integer with and suppose RIP of order holds with . If and are each at most -sparse and , then . More generally, if and , then
This compares any two sparse feasible vectors; it does not specify how to find either one.
When the support is not to be found but is handed to us, a sharper and simpler statement holds.
Proposition 16.4.3
(Known-support least squares)
Suppose , RIP of order holds with , and with . The unique least-squares fit on the given set satisfies
Its residual is , where is the orthogonal projector onto . Knowing is an oracle assumption, not a consequence of the fit.
Proof sketch or proof idea
Proof
(Sparse differences and the lower bound)
The difference has at most nonzeros. The lower RIP bound gives . If , the right side is zero. In the noisy case, . This proves both claims. Notice why order , rather than merely , matters: the two supports can be disjoint.
Proof
(The oracle fit is a projection of the noise)
The lower RIP bound makes injective. The normal equations therefore have the stated unique solution. The fitted error is a projection of the noise, so its norm is at most . Applying the lower RIP bound to the coefficient error proves the coefficient estimate , half the general two-feasible-vector bound. The remaining noise is orthogonal to the fitted error, so their squared norms add to . A small residual can coexist with a substantial coefficient error when noise lies in the fitted span.
Projecting selected columns
Let be pairwise disjoint and . Write and . RIP ensures is independent (and take ).
Lemma 16.4.4
(Projected restricted isometry and cross-correlation)
Under RIP of order with constant , for every indexed by and indexed by ,
and the norm bounds also hold with replaced by .
Proof
(Projection as a minimization, then polarization)
For a vector on , orthogonal projection minimizes distance to , so
The choice and upper RIP give . The same two bounds hold on the union . For the cross term, normalize nonzero to unit length and apply the two bounds to their sum and difference. Disjointness gives both coefficient vectors squared norm two; the polarization identity bounds four times the cross product by . Rescale. Zero vectors are immediate.
Proof X-ray
Why the projected columns inherit the isometry
The key move is to read as a minimum over all refits on . Each competitor is the image of one vector supported on , so the lower RIP bound applies to it with squared norm ; this is where is used, and the projection costs nothing in the lower constant. The upper bound needs only the single competitor .
The cross-correlation bound is a second, separate step. Polarization writes as the difference of and , so it needs the norm bounds on , hence the full count . Disjointness of and is what makes both have squared norm exactly two; without it the two error terms would not cancel to .
Thus even after refitting, projected disjoint signal groups have controlled cross-correlation. Suppose , where is indexed by and . The residual after least squares on is . Its false projected correlation obeys
The signal term follows from the lemma by taking a supremum over unit ; the noise term follows from Cauchy–Schwarz, the upper projected bound, and , because is an orthogonal projector. This is a bound for specified disjoint sets, not an OMP selection theorem: a selection proof must also give a strictly larger true correlation and deal with all competing indices and stopping.
The projected bounds also control the true proxy on , which is different from bounding a false-group correlation. Set . The projected RIP bounds show that every eigenvalue of this symmetric Gram matrix lies between and ; hence . Using and , we obtain
The first term measures distortion from the projected Gram matrix, and the second is projected noise. This estimate explains the proxy-error comparison in the worked example on projected proxies. It does not say the proxy equals the coefficient, and comparing true and false bounds still requires suitable coefficient sizes before a selection claim follows.
What changes when the signal has a tail?
Exact sparsity is an idealization: a measurement may contain a few large coefficients together with many small ones. Let keep largest-magnitude entries of , breaking ties in any fixed way, and set . This choice minimizes the Euclidean error among all -sparse approximations: for any chosen support, the best coefficients are those of itself, so retaining the largest squared magnitudes leaves the smallest sum of squares. However, the discarded tail still enters the measured data. In particular, , so from the perspective of an -sparse model, the effective noise is the sum of the physical noise and the measurement of the tail.
Proposition 16.4.5
(Least-residual sparse fit of a compressible signal)
Suppose , , and order- RIP holds with . Let minimize over all vectors with at most nonzeros, and set . Then
Proof
(The best sparse approximation is an admissible competitor)
A minimizer exists: there are finitely many supports of size at most , and on each the image of the corresponding submatrix is a closed finite-dimensional subspace, so an orthogonal projection supplies a minimizing fit. Since is an admissible competitor, . The triangle inequality and the RIP applied to the at-most--sparse vector now yield
The second inequality follows from .
The term is essential: even perfect recovery of leaves the discarded part of unreconstructed. The estimate remains valid for any support chosen among tied largest entries. It describes an ideal comparison, not an efficient search algorithm; it does not imply that a given numerical solver finds the best fit, nor is it a guarantee for an minimizer, whose analysis needs additional arguments.
Another ideal formulation minimizes subject to , with . The competitor is feasible, so every global minimizer has at most nonzeros and the two-feasible-vector theorem gives . Such a minimizer exists: take the smallest support size for which a feasible vector exists. The residual tolerance must cover the tail; using only does not necessarily make feasible. This formulation and the least-residual formulation above are different optimization problems, although both estimates use the same sparse-difference argument.
The term depends on the sensing matrix and can be difficult to evaluate without knowing the tail. There is nevertheless a simple deterministic bound. Order- RIP gives for every column. Expanding as a sum of columns and using the triangle inequality gives . This bound is often conservative because it ignores cancellation. A sharper deterministic bound uses blocks. Sort the nonzero entries of by decreasing magnitude and cut them into consecutive groups of size (the last possibly smaller). Order- RIP on each block and the fact that every entry of is at most the average magnitude on give
Summing over and using ,
A zero tail gives zero, and with a single block the second sum is empty. This bound does not require the tail to be sparse; either bound may be used, whichever is smaller.
Common mistake
(Applying the RIP inequality directly to a dense tail)
It is tempting to write . That step is unjustified when has more than nonzeros, because order- RIP says nothing about such vectors. The column-by-column bound remains valid for a dense tail. A small individual tail coefficient alone also need not make the total tail negligible when many are present.
Coefficient error and support decisions
A vector error bound turns into a support decision only together with a lower bound on the size of the true coefficients.
Corollary 16.4.6
(Support identification by thresholding)
Assume and order- RIP with . Suppose the true is exactly -sparse with support , and that and are both -sparse and fit to within . Set . If every nonzero entry of has magnitude strictly greater than , then .
Proof
(Coordinate errors are bounded by the vector error)
The uniqueness and noise stability theorem gives , hence every coordinate error is at most . Outside the magnitude of is therefore at most , while inside it is at least , which is strictly greater than . The threshold rule declares an index present only when its magnitude exceeds , so it returns exactly ; the strict inequality also removes ambiguity at the threshold.
This is sufficient, not necessary; the actual error may be much smaller than its bound. There is a basic obstacle when coefficients are too small. Suppose and has a unit column ; choose a nonzero scalar with . The observed data are consistent both with and no noise, and with and noise . Both noises meet the same bound, but the supports differ. No rule using only , and this noise bound can identify the support in both cases. This ambiguity persists even for the identity matrix, so it is not caused solely by poorly conditioned columns.
Worked examples
Worked example 16.4.7
(Two correlated columns)
Let and . The Gram matrix has eigenvalues and , so the order-two RIP constant is . Every one-sparse vector is uniquely identified by its exact measurement. With , and , a direct triangular solve gives . The coefficient error has norm , as the oracle bound predicts. The residual is zero because these two columns span ; zero residual has not removed the coefficient error.
Worked example 16.4.8
(A projected correlation)
Take unit columns , and . The full Gram eigenvalues are , so . With , and . Their inner product is zero and the bound gives . In contrast, , not one: projected columns should not silently be treated as normalized.
Worked example 16.4.9
(A projected proxy is not the coefficient)
Let , , , and . Here and . Refitting on gives and . Their correlation is , whereas the remaining true coefficient is one. Even with no noise, that correlation would be only : projection has changed the column length. Dividing by would give the one-column least-squares coefficient, but raw correlation is the quantity used in a correlation comparison. The true-proxy error bound above allows an error of , larger than the actual proxy error .
Worked example 16.4.10
(Sparse uniqueness alongside a nontrivial null space)
Consider
Every column has length one, so . Columns one and two have Gram matrix ; columns one and three, or two and three, have Gram eigenvalues . Hence , and no two distinct one-sparse vectors give the same exact measurement. Nevertheless satisfies , so for every
satisfies . At it is one-sparse; at all three entries are nonzero. The difference of the two solutions has support of size three, beyond the reach of order-two RIP, so there is no contradiction. Zero residual alone does not make an arbitrary solution close to the sparse truth.
Worked example 16.4.11
(A small tail acts as model error)
Take , , and . Thus , while and . The best one-sparse fit retains the largest magnitude entry of , giving . Here , and . The general bound is , whereas the actual distance is zero. The total error is the discarded tail. If instead one only uses the column bound, , which gives the looser . Neither bound predicts an equality.
Common mistakes
Counterexample mode
One-column conditioning cannot establish one-sparse uniqueness
Let for a unit vector . Every one-sparse vector obeys , so the order-one constant is zero. Yet . The order-two lower bound fails because is in the null space. Thus even perfect order-one conditioning does not prove uniqueness among one-sparse vectors.
RIP is a sufficient condition, not a necessary description of every successful instance. The definition does not itself provide an efficient way to compute . One direct approach examines the relevant column submatrices; our examples only compute the constant for very small matrices.
Common mistake
(Reading the oracle bound as support discovery)
The known-support estimate assumes that the correct is supplied. It does not assert that the fit finds , nor that tiny nonzero coefficients remain distinguishable from noise; the threshold corollary needs an explicit lower bound on the true magnitudes.
Common mistake
(Treating one false-correlation bound as a selection proof)
A bound on the projected correlation of one false group shows only that this group cannot correlate too strongly. A greedy choice is correct only if a true correlation is strictly larger than every false one, which also needs a lower bound for the true proxy and suitable coefficient sizes.
Summary
The lower restricted isometry controls sparse differences and makes known-support fitting stable; the upper bound also controls noise correlations. After projection, a minimization argument preserves restricted norm bounds on the remaining columns. These facts have different hypotheses and conclusions, and none should be confused with a complete sparse recovery algorithm.
Exercises
Quick check
(Suppose , , and two -sparse vectors each fit within in Euclidean norm. Bound their distance.)
Solution · Answer
The distance is at most . This is an upper bound; it does not assert that the distance between the vectors equals .
Quick check
(With , , true coefficient and noise , compute the oracle fit, coefficient error and residual. Verify the Pythagorean identity for the noise.)
Solution · Answer
The fit is , the coefficient error is , and the residual is . The fitted error and residual have squared norms and , summing to . The coefficient bound is because , and is below it.
Quick check
(For the projected-correlation worked example, calculate , and . Explain whether is independent of .)
Solution · Answer
The three values are , , and zero. The nonzero projected norm shows is not in the span of , so the pair is linearly independent despite their nonzero correlation.
Quick check
(Let with unit and . Give two distinct one-sparse exact fits. Explain why the uniqueness theorem does not apply.)
Solution · Answer
The vectors and both fit exactly. The nonzero difference is two-sparse and lies in the null space, so no order-two RIP constant smaller than one is possible.
Quick check
(Let , , and . Find a best one-sparse fit to , its error from , and the tail-based bound using the exact .)
Solution · Answer
The data are , so retaining the largest coordinate gives . Here and . The actual error is . Since and , the stated bound is . It is deliberately an upper bound; the fit need not attain it.
Quick check
(Suppose the hypotheses of the thresholding corollary hold with and . Give and a sufficient lower bound for every nonzero coefficient to be detected by thresholding at . Why does the proof not certify detection when a coefficient's magnitude equals exactly this lower bound?)
Solution · Answer
We have . The sufficient condition is that every nonzero coefficient have magnitude strictly greater than . At equality, the coordinate error could in principle reduce a true magnitude to exactly , while the rule retains only magnitudes strictly above ; the proof therefore cannot certify that case.