From uniqueness to a computable objective
A wide measurement matrix can identify a sparse vector uniquely among all sufficiently sparse vectors, yet searching through every possible support is combinatorial. Basis pursuit replaces the count of nonzero entries by the sum of their absolute values. Does this replacement preserve the answer? The answer depends on how every invisible perturbation distributes its mass, not just on whether a sparse null vector exists.
Definition 16.5.1
(Restriction to an index set and basis pursuit)
Let and . For , write for the vector equal to on and zero elsewhere; is the complementary set. For noiseless data , basis pursuit asks for a minimizer of
A minimizer exists: the feasible set is nonempty, and the intersection with the closed ball of radius is compact. Every feasible point outside that ball has objective greater than , so a minimizer on the intersection is global. It need not be unique. All statements here concern real vectors and exact arithmetic; this constrained problem is not the penalized lasso with a positive penalty parameter.
The exact criterion
Since two feasible vectors differ by an element of , every question about basis pursuit is a question about how null vectors spread their mass.
Definition 16.5.2
(Strict null-space property of order )
The matrix has the strict null-space property of order if, for every nonzero and every with ,
If the property holds vacuously.
Theorem 16.5.3
(Null-space characterization)
The following are equivalent:
- For every with at most nonzero entries, is the unique basis-pursuit minimizer for .
- has the strict null-space property of order .
Proof
(Sufficiency by the reverse triangle inequality; necessity by splitting a null vector)
Assume the strict property. Let be supported on , , and let another feasible vector be . Then . If , the reverse triangle inequality on gives
Thus every distinct feasible vector has strictly larger objective, proving uniqueness.
Conversely, suppose the property fails. There are in the kernel and with . Set and . Then , so , while . Since , is not the unique minimizer: either it is beaten or it ties another feasible vector. This proves necessity.
Proof X-ray
Where strictness and the order $s$ enter
Sufficiency uses two facts only. First, a feasible competitor differs from by a null vector . Second, vanishes on , so on the competitor pays the full mass , while on the reverse triangle inequality says it saves at most . The strict inequality turns "saves at most" into a strict net loss for every ; a non-strict inequality would only give , which allows ties.
The non-obvious move is in necessity. A bad null vector is cut along into and . The first piece has at most nonzero entries, so it is a legitimate test signal in statement 1; this is the only place where the order is used. The second piece produces the same measurement because their difference is . Equality already produces a tie, which is why statement 2 cannot be weakened to when uniqueness is demanded.
The property implies that no nonzero null vector is supported on at most coordinates: split such a support into two sets of size at most and apply the strict inequality to each. Thus each -sparse is the only -sparse solution of . The converse fails, as the following explicit matrix shows.
Counterexample mode
Sparse uniqueness without the null-space property
Claim: if no nonzero null vector is supported on at most coordinates, then basis pursuit recovers every -sparse vector. Take and
Every nonzero null vector has all three entries nonzero, so the hypothesis of the claim holds. For the mass inside and outside is in both cases, so the strict property fails. Concretely, and give and both have norm . Both are minimizers: any feasible satisfies , so . Hence is not the unique minimizer. The correct condition is the -mass inequality of the theorem, not the support count.
A tail bound for a non-sparse signal
Exact sparsity is an idealization. A useful guarantee should degrade gracefully when the signal is only close to sparse.
Definition 16.5.4
(Best -term error)
For an arbitrary ,
An index set of largest magnitudes, with ties chosen arbitrarily, is a minimizing set. It is an analysis device: the reconstruction does not need to know it.
Theorem 16.5.5
(Deterministic instance bound)
Suppose that for some , every and every satisfy . For any and any basis-pursuit minimizer of the exact data ,
Proof
(Comparing the minimizer with the true signal)
Put and choose a best set . Feasibility gives , and optimality gives . Applying the reverse triangle inequality separately on and yields
Hence . Using the assumed inequality, . Finally,
This bound is deterministic and for exact measurements. It neither assumes nor establishes a bound under measurement noise; noisy data require an appropriate robust hypothesis and a modified feasible set.
Common mistake
(Reading the exact-data bound as a noise bound)
With data and , the true is usually not feasible for . The proof above used feasibility of twice: to get and to compare with . Neither step survives, so the inequality says nothing about noisy data until the constraint is relaxed and the null-space hypothesis is strengthened to a robust one.
Worked examples
Worked example 16.5.6
(One invisible direction)
Take
For any nonzero kernel vector and any singleton , the mass inside is and outside it is . The strict property holds for , as does the quantitative condition with the sharp constant : every one-sparse vector is uniquely recovered. In particular, produces and is the unique minimizer.
The same data have another sparse representation , whose norm is rather than . Thus basis pursuit cannot recover this two-sparse : the feasible vector has smaller objective. The guarantee for one-sparse signals must not be silently extended to two-sparse signals.
Concept lensAnalytic
A dual certificate for one signal at a time
The null-space property is uniform over all -sparse signals. Convex duality gives a test for one fixed with support : is the unique basis-pursuit minimizer exactly when the columns of indexed by are linearly independent and some satisfies
For the matrix above and , gives , certifying recovery. For , the requirement forces or , matching the tie found there.
Worked example 16.5.7
(The instance bound for a nearly one-sparse signal)
Keep the same , and , so the constant is . Let ; then and . Every feasible vector is , with objective
A sum of absolute deviations is minimized exactly at the median of the points , so the unique minimizer is with , compared with for the true signal. Hence and , so
The intermediate inequality also checks: with , . Basis pursuit did not return , but its error is controlled by the tail .
Worked example 16.5.8
(Edge case: order equal to the ambient dimension)
Let . Then is allowed and , so the strict property would require for each nonzero . That is impossible, so the strict property of order holds exactly when , which forces . In that case the feasible set is the single point , and recovery is trivial. Also for every , so the instance bound reads . A wide matrix () can therefore satisfy the property only for some orders .
Common mistake and solved practice
Common mistake
(A sparsest solution need not be the unique ℓ1 minimizer)
“A feasible solution with the smallest support must also be the unique minimizer.” The theorem requires a statement about every null direction. For the matrix above, is the unique one-sparse solution of its system, and hence the unique sparsest solution, yet it ties the denser solution for the smallest norm. Equality in the criterion is not enough.
Quick check
(For the matrix of the first worked example, does the strict null-space property of order hold?)
Test the kernel vector against a two-element set.
Solution · Answer
No. For and , while . The splitting construction gives and , which are exactly the two representations and of the same data, the second with smaller norm.
Quick check
(Compute and for .)
Keep the entries of largest magnitude and add the remaining magnitudes.
Solution · Answer
For keep the entry , leaving , so . For keep and , leaving , so .
Quick check
(If the hypothesis of the instance bound holds with and , what can be said about ?)
Apply the hypothesis to every singleton set.
Solution · Answer
With , every satisfies for each single index . Hence and . The feasible set is then , so , which is consistent with the bound .