Nullspace property

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of \ell_1 -relaxation. The term "nullspace property" originates from Cohen, Dahmen, and DeVore. The nullspace property is often difficult to check in practice, and the restricted isometry property is a more modern condition in the field of compressed sensing.

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of \ell_1 -relaxation. The term "nullspace property" originates from Cohen, Dahmen, and DeVore. The nullspace property is often difficult to check in practice, and the restricted isometry property is a more modern condition in the field of compressed sensing. \min\limits_{x} \|x\|_0 subject to Ax = b , is a standard problem in compressed sensing. However, \ell_0 -minimization is known to be NP-hard in general. As such, the technique of \ell_1 -relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the \ell_0 -norm. In \ell_1 -relaxation, the \ell_1 problem, \min\limits_{x} \|x\|_1 subject to Ax = b , is solved in place of the \ell_0 problem. Note that this relaxation is convex and hence amenable to the standard techniques of linear programming - a computationally desirable feature. Naturally we wish to know when \ell_1 -relaxation will give the same answer as the \ell_0 problem. The nullspace property is one way to guarantee agreement. An m \times n complex matrix A has the nullspace property of order s , if for all index sets S with s=|S| \leq n we have that: \|\eta_S\|_1 for all \eta \in \ker{A} \setminus \left\{0\right\} . \textbf{Theorem:} Let A be a m \times n complex matrix. Then every s -sparse signal x \in \mathbb{C}^n is the unique solution to the \ell_1 -relaxation problem with b = Ax if and only if A satisfies the nullspace property with order s . \textit{Proof:} For the forwards direction notice that \eta_S and -\eta_{S^C} are distinct vectors with A(-\eta_{S^C}) = A(\eta_S) by the linearity of A , and hence by uniqueness we must have \|\eta_S\|_1 as desired. For the backwards direction, let x be s -sparse and z another (not necessary s -sparse) vector such that z \neq x and Az = Ax . Define the (non-zero) vector \eta = x - z and notice that it lies in the nullspace of A . Call S the support of x , and then the result follows from an elementary application of the triangle inequality: \|x\|_1 \leq \|x - z_S\|_1 + \|z_S\|_1 = \|\eta_S\|_1+\|z_S\|_1 , establishing the minimality of x . \square

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1190316981 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001190316981 · captured 1702790510.0 · version history

Cite this page as: encyclopegia.org, “Nullspace property”, snapshot enwiki-001190316981. https://encyclopegia.org/a/nullspace-property

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.