Motivation
A greedy approximation method chooses one promising dictionary element at a time. Its practical appeal is that a correlation calculation can be much cheaper than searching all subsets. But a large correlation can come from a misleading combination of several true elements. To prove that the greedy choices identify a sparse representation, we need a condition that prevents an incorrect atom from imitating the whole true support too well.
The earlier pursuit note derived residual updates and contrasted ordinary matching pursuit with orthogonal refitting. Here we add a complete recovery argument. The setting is finite, deterministic and noiseless for the main theorem. A bound on pairwise atom correlations will imply linear independence of small subsets, uniqueness of sparse coefficients, and correctness of every OMP selection. These are separate statements, and each needs a proof.
We also examine the theorem's boundary. A sufficient coherence threshold is not necessary; failure of the threshold does not prove algorithmic failure. Conversely, a unique sparse representation alone does not force greedy selection to succeed in the prescribed number of steps. Finally, sampled dictionary vectors are not automatically a stable representation of continuous functions. Exact recovery of a sampled vector and accurate approximation between sample points remain different mathematical questions.
Definitions
Definition 16.1.1
(Coherence of a normalized dictionary)
Let be a finite real dictionary whose columns satisfy . Its coherence is ; define when . A support is a set of distinct column indices, and an -sparse coefficient vector has at most nonzero entries. The true support below contains exactly entries, all with nonzero coefficients.
For a selected set , the orthogonal least-squares fit minimizes . When its columns are independent, the coefficients are unique and its residual is , where projects onto their span. This residual is perpendicular to every selected atom. Independence here is linear independence of deterministic vectors, not probabilistic independence of observations.
Definition 16.1.2
(Orthogonal matching pursuit)
Orthogonal matching pursuit, or OMP, starts with and . At each nonzero residual, choose an unselected index maximizing , add it to , refit all selected coefficients by least squares, and recompute the residual. A fixed tie rule, such as the smallest index, makes the algorithm definite. Stop at zero residual or at a specified budget. The theorem uses exact arithmetic and a budget of at least .
This refit is essential. Ordinary pursuit adds a multiple of one atom without necessarily restoring orthogonality to earlier atoms. Our invariant and induction use the orthogonal projection after every selection. Normalizing atoms is likewise part of the problem; otherwise raw correlation also measures arbitrary column length.
Theorem/proposition
Theorem 16.1.3
(Coherence controls independence and sparse uniqueness)
For any subset of atoms, its Gram matrix satisfies
If , the subset is linearly independent. In particular, if , every vector has at most one coefficient representation with at most nonzero entries.
Uniqueness says what a greedy method should find; the second theorem says when OMP actually finds it.
Theorem 16.1.4
(A complete noiseless OMP recovery guarantee)
Suppose has exactly nonzero coefficients and
OMP chooses only indices in and recovers all coefficients exactly after selections. Its residual cannot become zero earlier. Ties between true atoms do not hurt the guarantee; the proof gives a strict gap between the largest true correlation and every false correlation.
Proof sketch or proof idea
Proof
(Gram bounds, independence and sparse uniqueness)
For the first theorem, expand into diagonal terms and cross terms. The diagonal sum is ; the absolute cross contribution is at most . The identity , together with , bounds that sum by . This proves both Gram inequalities and independence when the lower factor is positive.
If two coefficient vectors with at most entries represent the same signal, their difference is supported on at most columns. Under the strict coherence condition those columns are independent by the same estimate, so the difference is zero. This proves uniqueness; it does not yet prove that a greedy algorithm finds the representation.
Proof
(Induction on correct OMP selections)
Assume OMP has selected a proper subset of the true support. Its orthogonal residual lies in the span of . Write ; this coefficient vector is unique because the true columns are independent. The residual is nonzero: otherwise a proper subset of would represent the signal, contradicting independence and the assumption that every true coefficient is nonzero.
Pick an index where . Its true-atom correlation is at least . Every false atom has correlation at most . The first factor exceeds the second exactly under the displayed condition. Selected atoms have zero correlation by the refit invariant, so a largest true correlation must occur at an unselected true atom. The next choice is therefore correct.
After such steps the selected set is exactly . Its least-squares fit equals the true signal and its unique coefficients equal . This completes recovery. The proof is uniform over coefficient magnitudes in the exact noiseless model; it does not supply the same support guarantee in the presence of arbitrary noise.
Proof X-ray
Where each hypothesis enters the induction
Three facts are used at three different places. The span invariant, that all earlier choices were correct, keeps the residual of the form ; only then is the coherence comparison available, and the second worked example shows how one wrong choice destroys it. The strict condition is used exactly once, to separate the true lower bound from the false upper bound ; because the gap is strict, ties among true atoms are harmless. Orthogonal refitting makes the correlations with selected atoms zero, so the winning true correlation belongs to a new atom. Linear independence of the true columns makes unique and rules out a zero residual before step . None of these can be replaced by the mere observation that the residual norm decreases.
If the correct support is supplied and data instead equal with , refitting gives coefficient error at most . Indeed the coefficient change is the least-squares response to , and the first theorem bounds the smallest singular value. Its reconstructed signal error is at most , since it is the orthogonal projection of . These are conditional known-support bounds, not a proof that noisy OMP discovers that support.
The strictness of the coherence condition is not a technicality, as an explicit configuration at the boundary shows.
Counterexample mode
At the coherence boundary a tie can select a false atom
Claim: the guarantee survives at the boundary . Take and the unit vectors
Then and , so and . Let and . The three correlations are , and . With the smallest-index rule OMP selects the false atom . The residual is , whose correlations with and are both , so atom two is chosen next. Both selected atoms lie in the plane of the first two coordinates, while has third coordinate , so the residual is nonzero after selections. A third step would select and refit with coefficient zero on , but the promised recovery in exactly true selections has failed. The repaired statement is the theorem as stated, with the strict inequality .
Worked examples
Worked example 16.1.5
(A guaranteed nonorthogonal recovery trace)
Take , , , and . The coherence is , so the theorem covers two-sparse signals. Let . Initial correlations are , , and , so the first choice is atom four.
Its first coefficient is and the residual is . The new correlations are . Thus atom one is selected next. Refitting the two selected atoms returns coefficients one and two on atoms one and four, and residual zero. The first coefficient on atom four changes during refitting; freezing it at its first value would not be OMP.
Worked example 16.1.6
(A unique sparse representation can still mislead OMP)
In , take , and . These three columns are independent, so the signal has a unique representation in the whole dictionary. Its initial correlation with the false atom is , larger than either true correlation. OMP selects atom three first.
The first residual is . With the smallest-index tie rule, the second selection is atom one. The orthogonal refit has coefficients on atom one and on atom three, yielding residual , still nonzero after two steps. The coherence condition fails, and uniqueness alone did not repair the wrong first choice.
Worked example 16.1.7
(Noise needs a different identification statement)
For the support of the first worked example, the Gram eigenvalues are and . If this support is known and noise norm is at most , the coefficient error is at most . The reconstructed signal error is at most . These estimates separate coefficient conditioning from signal accuracy.
Even an orthonormal dictionary cannot recover arbitrarily small nonzero coefficients under arbitrary bounded noise. For a signal , noise produces the same observed vector as the noiseless signal . When , both explanations satisfy the noise allowance. A coefficient lower bound is needed to exclude this cancellation, but is not sufficient by itself: a noisy selection analysis must also establish correct choices. Alternatively, one can use a success criterion that does not require exact support identification.
For a dense dictionary, each correlation scan costs . A straightforward new QR factorization at every step costs a total over selections, in addition to the scans. Maintaining an orthonormal selected basis incrementally reduces the refit work to , giving total work . The extra stored factors require numbers beyond the dictionary. These are arithmetic counts, not an assertion that all floating-point implementations have equal stability.
Common mistakes
Common mistake
(Treating the coherence threshold as a necessary condition)
The coherence condition is sufficient, not necessary. Dictionaries violating it may recover many particular signals, so failure of the threshold does not prove algorithmic failure. At the equality boundary the strict comparison disappears and the theorem gives no guarantee, as the boundary configuration above shows. A numerical correlation tie should not be silently treated as the strict separation required by the proof, and exact-zero stopping needs a tolerance in an implemented noisy procedure.
Common mistake
(Normalizing a sampled function that vanishes at every node)
To use a continuous dictionary from sampled data, first form weighted sample vectors and normalize their nonzero norms. Their coherence concerns that sampling geometry. A function vanishing at all nodes gives a zero vector and cannot be normalized into an atom. Continuous independence does not prevent this loss of information at a poor set of nodes.
Common mistake
(Reading sampled orthogonality as continuous accuracy)
Suppose a finite function span satisfies a lower norm comparison with . Then a sampled reconstruction error for a difference inside that span implies continuous error at most its sampled norm divided by . Coherence alone does not provide this comparison for an arbitrarily chosen continuous norm; the fourth exercise has coherence zero and still amplifies error. A target outside the span also has an approximation residual whose sampled aliasing must be treated separately.
Summary
Normalized finite dictionaries admit a transparent coherence analysis. Small-subset conditioning yields sparse uniqueness, and a separate strict-correlation argument proves every step of noiseless OMP recovery. Orthogonal refitting supplies the invariant needed for the induction. Noise, finite precision and the passage from sampled vectors to continuous functions require additional information beyond that exact recovery theorem.
Exercises
Quick check
(A normalized dictionary has coherence and enough columns for the subsets considered. What is the largest integer sparsity covered by the strict theorem? Bound the squared singular values of any three-column subdictionary.)
Solution · Answer
The condition is , so and the largest covered integer is two. For three columns, squared singular values lie between and . At sparsity three equality would occur, so the strict theorem does not apply.
Quick check
(Using the dictionary of the first worked example and its smallest-index tie rule, trace OMP for . Give both selected atoms, refitted coefficients and residuals.)
Solution · Answer
Initial correlations are one, one, zero and , so atom one is selected. Its coefficient is one and residual is . Next correlations among unselected atoms are one, zero and , so atom two is chosen. Refitting the orthonormal pair gives coefficients one and one and residual zero.
Quick check
(Explain the identifiability obstruction when bounded noise can cancel a true coefficient. Why does coherence zero not remove it? State one kind of extra assumption needed for an exact noisy-support guarantee.)
Solution · Answer
The observations from with noise equal those from without noise. If lies within the noise allowance, no procedure can distinguish these explanations from that observation alone. Orthogonality makes noiseless directions distinct but cannot reveal a canceled signal. A lower bound on nonzero coefficient magnitude relative to noise is necessary to exclude this cancellation. It is not sufficient alone: an appropriate noisy selection analysis is also needed before the combined assumptions can yield a recovery guarantee.
Quick check
(Sample the continuous functions one and at with probability weight at each node, where . Find the coherence of their normalized sampled vectors. If the two observed responses are perturbed by , find the resulting continuous error under uniform probability measure on .)
Solution · Answer
With weight at each node, the normalized sampled atoms are and , so coherence is zero for every positive . The response perturbation is fitted by the function . Its continuous norm is , while its weighted sampled norm is . Thus perfect sampled orthogonality does not prevent continuous error amplification as the nodes collapse toward the origin.