Sparse recovery and restricted eigenvalues

Basis pursuit minimizes the sum of absolute coefficient values subject to exact noiseless measurements. Although the target is sparse, the optimization searches all coefficient vectors. Excluding a sparse null vector establishes uniqueness among sparse candidates, but does not by itself prove that no dense candidate has a smaller absolute-value sum. For a fixed support, the null-space property supplies exactly the comparison needed: any nonzero invisible displacement must have more absolute mass outside that support than inside it.

To prove sufficiency, compare a supported target with that target plus a null displacement. The triangle inequality bounds the penalty decrease on the support by the displacement mass there, while outside the support the penalty increases by its full mass. The strict inequality makes the total increase positive. Conversely, if it fails, take a target equal to minus the displacement on the support. Its alternative equals the displacement off the support and has no larger penalty. Thus strictness characterizes recovery of every target on that support, not merely one favorable target.

With noise and regularization, an estimator generally has small but nonzero coefficients outside the true support. Its error is therefore not guaranteed sparse. A basic inequality can instead place the error in a cone where the outside absolute mass is at most three times the inside mass. The factor three is a consequence of a particular noise-to-penalty comparison; it is not an intrinsic geometric constant. A restricted-eigenvalue condition must specify which cone and which norm appear, since several conventions are used in the literature.

Here use the stronger full-error convention in the display: on the cone, the normalized prediction norm is at least a fixed positive constant times the full Euclidean coefficient norm. A wide matrix can satisfy this restricted lower bound even though its unrestricted smallest singular value is zero. The null space is allowed, but it must avoid the cone except at zero. This geometry converts prediction control into coefficient control precisely for error directions generated by the estimator’s penalty argument.

An injective map on a collection of sparse vectors need not separate their images by a useful quantitative margin. Nearly repeated columns can make distinct sparse coefficients produce almost identical responses. Noise then hides their difference even though exact noiseless measurements would distinguish them. Restricted lower bounds rule out this instability on specified directions. They are assumptions about the actual design or high-probability consequences of a stated random-design model, rather than automatic consequences of having many observations.

Restricted isometry is another, usually stronger, sufficient framework: it controls both upper and lower distortion of every vector up to a specified sparsity. Suitable orders and constants can imply stable convex recovery, but a number quoted without its order or convention is not a theorem. For present purposes, the null-space property and the explicit cone bound isolate two separate roles cleanly. One certifies which exact fit minimizes a penalty; the other controls how much coefficient error can hide behind a small prediction error.