Motivation
A sparse model identifies a signal using a small number of columns of a dictionary. The preceding note proved a noiseless guarantee for orthogonal matching pursuit (OMP). Real measurements are rarely exact, and two questions must now be separated. If an oracle tells us which columns are active, how much can noise change the fitted coefficients? If the support is unknown, when do the observed correlations themselves reveal it?
We answer the first question by ordinary least squares on the supplied support and the second by a single thresholding step. These are deterministic results: the noise may be adversarial and no probability distribution is assumed. They are not a theorem that noisy OMP selects the support. A sufficient condition for one procedure must not be transferred to another without a proof.
Definitions
Let have unit columns, and let be its coherence, as in the preceding note, with when . For an index set of size , contains those columns and is their Gram matrix. All norms on vectors below are Euclidean unless a subscript says otherwise.
Definition 16.2.1
(Noisy sparse model and its parameters)
The observation is , where is exactly the set of nonzero coefficients, , and . Its parameters are
Since each atom has norm one, Cauchy–Schwarz gives . These parameters are bounds or properties of the unknown signal, not quantities an algorithm is assumed to know. For support identification assume and that the number is known.
Definition 16.2.2
(One-step correlation thresholding)
Given and the sparsity , one-step correlation thresholding selects the indices with largest ; ties can be broken arbitrarily. It does not update residuals or refit before making this selection.
Theorem/proposition
Theorem 16.2.3
(Gram bounds and the known-support fit)
For every nonempty of size , every eigenvalue of satisfies
If , then has full column rank and the unique least-squares estimate on the given support satisfies
More precisely, the reconstructed-signal error is , with the orthogonal projector onto . The observed residual is .
Concept lensAlgebraic
The Gram bound as a disc statement
The eigenvalue interval can also be read off the entries of directly. The matrix is real symmetric, every diagonal entry is , and every off-diagonal entry is at most in absolute value. Gershgorin's disc theorem places each eigenvalue in a disc centered at some diagonal entry whose radius is the absolute off-diagonal sum of that row:
Symmetry makes real, so the disc collapses to the interval of the theorem. The middle quantity is never worse than the coherence bound, and it is smaller when only a few pairs of selected atoms are nearly parallel.
The second result concerns an unknown support. It compares correlations only, and the Gram bound returns at the end to control the refit.
Theorem 16.2.4
(A sufficient separation for one-step thresholding)
In the same model, if
then every true atom has strictly larger absolute correlation with than every false atom. Selecting the largest absolute correlations therefore recovers , irrespective of tie-breaking within . The margin itself implies ; refitting on the selected support therefore gives the two error bounds above.
Proof sketch or proof idea
Proof
(Quadratic-form bounds and the projection identity)
For , expansion of the quadratic form and the definition of coherence give
The last inequality is Cauchy–Schwarz: . Applying the resulting quadratic-form bounds to an eigenvector proves the eigenvalue bounds. If the lower bound is positive, forces whenever . The normal equations then have the unique solution displayed above.
Set . The least-squares normal equations say . Thus , and by orthogonal projection. Combining this with gives the coefficient bound. Subtracting the fitted value from instead gives the different vector .
The thresholding proof uses no eigenvalue at all until its last line; it is a comparison of two families of inner products.
Proof
(Comparing the weakest true and the strongest false correlation)
For a true index , the reverse triangle inequality and yield
For a false index , the triangle inequality gives
Since and , the assumed margin implies , hence . The assumed strict inequality also makes the first bound strictly larger than the second. Hence no false index can enter the top , and all true indices must be selected. The argument proves a uniform comparison, including the possibility of negative coefficients and adversarial noise; it does not require the true correlations to have their noiseless signs.
Proof X-ray
Where each hypothesis enters the comparison
Unit norms are used twice. In the own coefficient appears with factor , and every cross term is bounded by . They also give .
The key move is to avoid tracking individual signs. One lower bound holds for every true index and one upper bound for every false index, so a single number separates the two groups. The top- set is then determined however the true correlations are ordered among themselves.
The constant counts interference: a true atom meets the other true atoms, a false atom meets all of them. The noise enters once on each side, which gives .
The argument closes in two steps. Strictness rules out a tie across the groups, and knowledge of makes the algorithm stop after exactly the true atoms. The separation alone does not give an algorithm when is unknown: placing a cut-off between the two bounds would require the unknown signal parameters. Finally, converts the margin into , so the first theorem applies to the refit without a further hypothesis.
The margin is sufficient, not necessary. Its use of the largest coefficient treats every interfering correlation as if it had its worst possible sign and magnitude simultaneously. It can therefore fail even when thresholding succeeds. If a bound is unavailable, replacing it by gives a weaker but directly valid condition. That replacement depends on normalized columns, as the following check shows.
Counterexample mode
Without normalized columns the noise bound fails
Claim: for orthogonal but unnormalized columns, the condition , with computed from raw inner products, still guarantees thresholding. Take in , , and . The raw inner products between distinct columns vanish, so , and .
The observation is . Its raw correlations with the three columns are , and . With , thresholding must select index together with one of indices , so it fails.
The broken step is : here exceeds because . Repair: normalize the dictionary by replacing with . The correlations become , and , and the strict margin certifies recovery of .
Worked examples
Worked example 16.2.5
(Select, then refit)
Take , , , , , and . Then , , , and . The condition holds because
The correlations are , , and . The first two are largest, so thresholding recovers . Refitting the orthonormal selected columns gives ; its coefficient and signal errors both have norm . The general coherence bound is , which is valid but conservative because the actual selected Gram matrix is the identity. The residual is zero: noise lying in the selected span is absorbed by the fitted coefficients.
Worked example 16.2.6
(Unique does not mean well conditioned)
Let and for . The columns are independent, so every vector in their span has a unique representation. Their Gram eigenvalues are . In particular, the coefficient vector has norm one while . As , two coefficient vectors a unit distance apart can produce arbitrarily close signals. Uniqueness is a yes-or-no property for each fixed positive angle; the inverse stability constant deteriorates without bound as the angle shrinks.
Worked example 16.2.7
(A unique representation need not survive thresholding)
Let , , and . The three columns are independent, so even the representation in the whole dictionary is unique. But their absolute correlations with are , , and . With , one-step thresholding chooses indices , not the true support . The sufficient margin fails here; uniqueness does not imply its conclusion.
Common mistakes
Common mistake
(A stable fit does not certify the support)
A positive Gram bound guarantees a stable fit for the given support; it does not tell us that the supplied support is correct. Choosing the support needs a coefficient-to-noise margin, which no conditioning bound supplies. Likewise, a zero least-squares residual does not establish noiseless observations, as the select-then-refit example shows. The condition is sufficient for independence, not necessary; its failure does not prove singularity.
Common mistake
(Treating the coefficient error as a part of the noise)
The noise splits orthogonally as , so . The coefficient error lives in , not in signal space; it is one of these components only after mapping by . Its norm can exceed , by a factor of at most .
Common mistake
(Accepting equality in the margin)
Equality in the two estimates does not rule out a true–false tie. In an orthonormal dictionary take , and . Then , and , so exactly. The observation has correlations and , and a tie-breaking rule may return the false index .
If noise cancels a nonzero coefficient, even an orthonormal dictionary cannot identify that support from the observation alone. Finally, this finite sampled-vector analysis says nothing by itself about errors between sampling nodes or about noisy OMP's sequential choices.
Summary
Coherence bounds all eigenvalues of a selected Gram matrix and hence controls the noise amplification of a known-support fit when its lower bound is positive. A separate comparison of every true and false correlation proves a support guarantee for one-step thresholding under an explicit strict margin. Both estimates are sufficient bounds, not characterizations of all successful dictionaries or signals.
Exercises
Quick check
(A normalized dictionary has . Bound the squared singular values and the 2-norm condition number of every four-column subdictionary. If the true support consists of four columns and , bound the known-support coefficient error.)
Solution · Answer
The Gram eigenvalues, equal to squared singular values, lie in . Hence every such subdictionary is injective and its 2-norm condition number is at most . The coefficient error is at most , approximately .
Quick check
(In an orthonormal three-column dictionary, let , , and . What is observed? Can any deterministic rule distinguish this explanation from another two-sparse explanation with the same noise allowance using only the observed vector?)
Solution · Answer
The observed vector is . It also arises from support with coefficients and noise . Both explanations have sparsity two and noise norm . A deterministic rule sees identical data in both cases and must give the same output, so it cannot be correct for both models even when is known. Here , , and , so the required strict margin fails. Cancellation shows why a noise-to-signal separation is needed for a uniform guarantee.
Quick check
(For in the dictionary of the select-then-refit example, take and . Calculate all correlations, the selected support for known , the refitted coefficients and residual. Does the sufficient threshold condition hold using the exact ?)
Solution · Answer
The correlations are , , and . The last is less than one, so thresholding chooses . The refitted coefficients are and the residual is . Here , so the sufficient condition reads , which holds.
Quick check
(Let . Prove that the potentially sharper condition also guarantees one-step thresholding. Explain why it is at least as permissive as the condition in the theorem.)
Solution
For a true index, . Every false correlation is at most . The stated condition makes the first bound strictly larger, proving recovery. Because one coefficient has magnitude and the other have magnitude at most , we have . Therefore
The original condition makes the right side positive. Thus it implies the new condition, which can hold in additional cases.