Compressed sensing reconstructs a sparse vector, or an approximately sparse one, from fewer linear measurements than its ambient dimension. Basis pursuit replaces counting nonzero coordinates by convex minimization. A null space property characterizes exact uniform recovery, while a robust null space property controls errors from noise and nonsparse tails.
The restricted isometry property controls uniformly over sparse vectors. It supplies quantitative near-orthogonality of disjoint sparse coordinate combinations, not merely normalization of individual columns.
The order-s restricted isometry constant is the smallest nonnegative satisfying for every vector with at most nonzero coordinates. Equivalently it is . The sparse-vector quantifier is essential, and the constant can equal zero.
For and , noisy basis pursuit has error , with constants depending only on . One admissible pair isThese constants follow from Theorem 3.3 of the sharp restricted-isometry recovery analysis, with the actual noise bounded by the tolerance . The restriction is necessary: equal unit columns give without unique recovery. The coefficient of the approximation term cannot universally be one.
Basis pursuit minimizes an norm subject to exact linear measurements. Basis pursuit with a noise tolerance replaces the equality by . A unique minimizer has linearly independent active columns, and hence at most nonzero coordinates: a null direction on its support would make the objective locally affine on a feasible line, contradicting minimality or uniqueness.
The null space property relative to is for every nonzero . It is equivalent to exact basis pursuit recovery of every vector supported in . Sufficiency follows from the triangle inequality; for necessity, compare and , which have the same image under . Recovery of a single fixed signed vector can hold without this uniform property.
The displayed property holds for every and every , with and . It converts the cone inequality from basis pursuit minimality and the tube inequality from noisy feasibility into a two-constant bound . Both constants are needed in general; a fixed coefficient one on the approximation term does not follow.
For a real vector with support , uniqueness in basis pursuit is equivalent to for every nonzero . The supporting-line inequality for the absolute value proves sufficiency. Taking small positive and negative multiples of before any active sign changes proves necessity.
A vector is s-sparse if it has at most nonzero coordinates. For , its best s-term approximation error is , equal to the sum of the absolute values of the coordinates outside the largest .
The support of a finite vector is the set of indices of its nonzero coordinates. It is the support of a function on a finite discrete index set, and its cardinality defines sparsity.
For any field and vector subspace , some has at least nonzero coordinates. Choose with largest support of a vector . Restriction from to is injective: a nonzero vector in its kernel of a linear map vanishes on , so adding it to would enlarge . Thus . The argument works over finite fields, where assuming a generic vector avoids finitely many hyperplanes would be invalid.
Articles by others on the same topic
Compressed sensing (CS) is a technique in signal processing that enables the reconstruction of a signal from a small number of samples. It leverages the idea that many signals are sparse or can be sparsely represented in some basis, meaning that they contain significant information in far fewer dimensions than they are originally represented in. ### Key Concepts of Compressed Sensing: 1. **Sparsity**: A signal is considered sparse if it has a representation in a transformed domain (e.g.