Motivation
A sensor rarely produces an exact linear measurement. If we insist on fitting noisy observations exactly, the fitted coefficients may explain measurement error instead of the underlying signal. On the other hand, allowing an arbitrary mismatch would make the zero vector an easy but uninformative answer. We need a tolerance that is large enough to contain the true signal yet small enough to retain information.
There are two independent obstacles to exact recovery. First, the observation may differ from . Second, a signal that is approximately sparse may have many small coefficients rather than exactly nonzero ones. This section derives a bound with a separate term for each obstacle. Its hypothesis controls not only invisible changes in the null space but also changes that are nearly invisible to the measurement matrix. The constants depend on that matrix; the result is deterministic and does not require a probability model for the noise.
Definitions
Work over the real numbers and in exact arithmetic. Let , , and write for the vector equal to on and zero elsewhere. The complement is .
Definition 16.6.1
(Best -term tail and noisy basis pursuit)
For a signal , define
Suppose with , where is a specified bound. Noisy basis pursuit chooses any global minimizer of
A set containing largest-magnitude coordinates attains the minimum: exchanging a retained smaller magnitude for a discarded larger magnitude cannot increase the discarded sum. Ties can be broken arbitrarily. This best set is used to analyze the answer; the reconstruction procedure does not need to know it. When two coordinates tie in magnitude and only one can be kept, both choices attain the same tail; the proof fixes one of them, and since the hypothesis below holds for every eligible set, ties do not affect the conclusion. When is unknown, so are this set and the tail: the theorem relates reconstruction quality to compressibility of the signal; it is not an error certificate computable from the data alone.
Why two different norms? In coefficient space the norm sums absolute values: it measures total error and biases the minimization toward economical representations. In data space the norm measures the residual as the Euclidean length of one vector. The two act on different spaces and cannot be equated; the constant in the robust property is part of what connects their scales. Changing measurement units or rescaling changes the admissible .
The true is feasible. Consequently, the feasible set intersects the closed ball of radius . This intersection is compact in finite dimensions, and a continuous objective attains its minimum there. A point outside that ball cannot improve upon the feasible point , so a global minimizer exists. It need not be unique; the result below applies to every minimizer.
Definition 16.6.2
(Robust null-space property)
The matrix has the robust null-space property of order with constants and if, for every and every with ,
This is an assumption about all vectors and all eligible supports, not a property of every matrix. For it reduces to a quantitative ordinary null-space inequality. For a general , the extra term measures how visible the change is. Knowing only a qualitative null-space statement does not supply the constants above for a noise calculation. Nor does checking a few supports or a few trial vectors establish the universal inequality.
Concept lensGeometric
Exact recovery as a kernel avoiding a cone
For exact data the minimizers are the points where the smallest ball, a cross-polytope, touches the affine set . Thus is the unique minimizer exactly when no nonzero satisfies : the kernel meets the descent cone of the norm at only at the origin. The null-space inequality with gives for every nonzero kernel vector, hence for every supported on : one condition on excludes the cones of all -sparse points at once.
Theorem: separating tail and noise
Theorem 16.6.3
(Stable recovery from bounded noise)
Assume the robust null-space property just stated. Let with , and let be any global minimizer of noisy basis pursuit with that tolerance. Then
The first term is the price of approximating by an -sparse vector; the second is the price of tolerating measurement error. They have different units and different origins. If is -sparse, the first term vanishes. If the data are exact and , the second vanishes. When both vanish together, the bound becomes an exact recovery statement.
Corollary 16.6.4
(Exact and unique recovery of sparse signals from exact data)
Under the robust null-space property of order , if has at most nonzero entries, and , then is the unique minimizer of noisy basis pursuit.
Proof
(Both terms of the bound vanish)
Here and , so the theorem gives for every minimizer . A minimizer exists by the compactness argument above, so the set of minimizers is exactly . Uniqueness is a conclusion here; it was not assumed in the theorem.
Since , the same right side also bounds the Euclidean error. It is generally not the sharper Euclidean estimate obtainable under stronger hypotheses. A theorem with a smaller or differently scaled term needs its own proof.
Proof: a cone and a measurement bound
Proof
(A cone inequality, a measurement bound and the robust property)
Put and let contain largest-magnitude entries of . Because is feasible and minimizes the objective,
Apply the reverse triangle inequality on and separately. On it gives ; on the complement it gives . Combining them with optimality and canceling yields the cone inequality
The factor two is not an arbitrary allowance: one copy of the tail appears on each side before rearrangement. The inequality says that a minimizer cannot put much more error outside the large coordinates than inside them unless the original signal had a sizeable tail.
Both and are feasible, so
The residuals can point in opposite directions, which explains the factor two. They need not be equal: generally .
Using the robust property, the cone inequality, and then the measurement bound,
Because , division gives
The cone inequality also gives . Substitution and simplification prove the displayed bound:
Proof X-ray
Where each hypothesis enters
The proof has three inputs, each used once. Optimality of against the feasible competitor gives the cone inequality; this is the only place the objective is used, and it is why the tail appears, once from each side of the reverse triangle inequality. Feasibility of both and gives ; this is the only place the noise level is used. The robust property is the bridge: it is applied to the actual error , which is generally not in , so its term is exactly what absorbs the measurement bound.
The closing move is algebraic but essential. The robust inequality bounds by a multiple of itself plus known terms, and only allows that term to be moved to the left. With the inequality would be consistent with arbitrarily large , as the boundary counterexample below shows.
Common mistake
(Using a kernel-only null-space bound for noisy data)
With , two feasible vectors usually differ by an with . A null-space inequality that controls only says nothing about this , so it cannot replace the robust property; neither can a qualitative null-space statement without the constants and .
Worked examples
Worked example 16.6.5
(A known matrix, a tail and noisy data)
Take , , , , and . The noise is , so the stated tolerance is valid. For every and singleton , ; thus , are valid constants.
Any feasible satisfies . Hence . The point is feasible and attains that lower bound; equality also forces and , so this minimizer is unique. The best one-term tail is and the actual error is . The theorem gives . A correct upper bound need not be tight for a particular signal and observation.
Worked example 16.6.6
(A genuinely underdetermined matrix)
Let
Its null space is , so there are infinitely many vectors with the same measurement. Nonetheless, it has the robust property with and . To verify it for every , put . For , triangle inequalities followed by Cauchy–Schwarz give
For , exchange and . For ,
The empty set is trivial, so the claimed constants work for all sets of size at most one. We have not claimed that is optimal. For and exact data , the theorem says that is the unique minimizer even though has a nontrivial kernel.
Worked example 16.6.7
(Edge case: exact data, yet the discarded tail changes the answer)
Keep the preceding and take , , with and . Every feasible vector has the form . Its objective is , minimized at the median of the three breakpoints . Thus the unique minimizer is , and
The result is not exact despite exact observations, because the original vector is not one-sparse. The tail term in the theorem allows this behavior; it does not claim the factor six is attained here.
Worked example 16.6.8
(An allowed residual can shrink the answer)
With the same , take , noiseless data , but permit . Feasibility implies , and therefore
The vector is feasible and attains this bound. In fact it is the only minimizer: equality forces the first fitted coordinate to be and ; the residual ball then forces the second fitted coordinate to be zero, so . Its error is . The guarantee is , since the tail is zero. A conservative tolerance can introduce reconstruction error even when the actual noise happens to vanish.
When assumptions fail
Counterexample mode
Equality at the null-space boundary is not enough
For , , , and , both and are global minimizers: any feasible has . The kernel vector has equal mass on and off , while . Hence the robust property fails for every , regardless of . Merely permitting would not support exact recovery or the division in the proof.
Common mistake
(Declaring a noise bound smaller than the actual noise)
Let , , , and incorrectly declare . The only feasible point is . Although the identity satisfies a robust property and is one-sparse, the proposed zero-error conclusion is false: the actual noise is , so is not feasible. The theorem has not failed; its premise has. Estimating or bounding noise is a separate modeling task.
Common mistake
(Treating the tolerance as a LASSO penalty)
Noisy basis pursuit imposes a residual constraint. Penalized LASSO instead minimizes a sum of residual loss and an penalty. Their solutions can be related under additional conditions and a suitable choice of parameters, but is not automatically a LASSO penalty, and the theorem above is not a theorem about LASSO.
Likewise, a numerical solver returning an approximately feasible or approximately optimal point needs a bound that includes those tolerances; exact optimality should not be silently attributed to a finite computation. Verifying the robust property itself can be difficult. A favorable example does not certify an arbitrary dictionary, and no probability, random-design or restricted-isometry guarantee follows without further hypotheses.
Exercises
Quick check
(For the matrix of the underdetermined worked example, let and . Calculate the theorem's numerical upper bound on error. Does it prove that the support is exactly recovered?)
Solution · Answer
Here and , so the tail and noise coefficients are respectively and . The bound is , about . An error bound alone does not prove exact support recovery: arbitrarily small nonzero coefficients may be introduced or erased. Additional thresholds and magnitude assumptions would be needed.
Quick check
(For the same matrix and exact observation , determine the noisy basis-pursuit minimizer when , knowing the true vector is one-sparse. Explain why it is unique without enumerating every feasible vector.)
Solution · Answer
The one-sparse vector has the specified measurement. Its best one-term tail and the tolerance are both zero. The theorem therefore forces every minimizer to equal this vector. Existence follows from the compact-sublevel argument above, so it is the unique minimizer even though the feasible set contains other, nonsparse vectors.
Quick check
(Let , , , and . Identify the actual noise, solve the constrained problem, and state exactly why the recovery theorem cannot be applied.)
Solution · Answer
The actual noise is , whose norm is . The constraint makes the unique minimizer. The true signal is infeasible, so the optimality comparison with and the measurement bound are unavailable.
Exercise 16.6.9
(Suppose the hypotheses of the theorem hold except that a feasible computed vector obeys for a known . Prove the bound below, and say what it requires about the computed residual.)
SynthesisProof
Solution(4)
- 1
Redo the cone inequality with the objective excess
Set and choose a best set . The same reverse-triangle calculation now yields .
- 2
Keep the measurement bound
.
Because: Both and satisfy .
- 3
Apply the robust property and solve for the on-support mass
Key step
Because: lets the term move to the left.
- 4
Combine and read off the residual requirement
∎Since , substitution gives coefficients , and . The guarantee requires ; a larger computed residual calls for a revised measurement bound.
Related notes
The null-space property for exact data explains uniqueness for noiseless basis pursuit. Proximal gradient for LASSO treats a different, penalized objective and a computable optimization certificate.