Restricted isometry property
Encyclopedia
In linear algebra
, the restricted isometry property characterizes matrices which are nearly orthonormal, at least when operating on sparse
vectors. The concept was introduced by Emmanuel Candès
and Terence Tao
and is used to prove many theorems in the field of compressed sensing
. There are no known large matrices with bounded restricted isometry constants, but many random matrices have been shown to remain bounded. The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices. Web forms to evaluate bounds for the Gaussian ensemble are available at the Edinburgh Compressed Sensing RIC page.
such that, for every m × s submatrix As of A and for every vector y,
Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant
.
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, the restricted isometry property characterizes matrices which are nearly orthonormal, at least when operating on sparse
Sparse
In computer science, Sparse is a tool designed to find possible coding faults in the Linux kernel. This static analysis tool differed from other such tools in that it was initially designed to flag constructs that were only likely to be of interest to kernel developers, e.g...
vectors. The concept was introduced by Emmanuel Candès
Emmanuel Candès
Emmanuel Jean Candès is a professor of mathematics and statistics at Stanford University.-Academic biography:Candès earned a B.Sc. from the École Polytechnique in 1993. He did his graduate studies at Stanford, where he earned a Ph.D. in statistics in 1998 under the supervision of David Donoho and...
and Terence Tao
Terence Tao
Terence Chi-Shen Tao FRS is an Australian mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory...
and is used to prove many theorems in the field of compressed sensing
Compressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
. There are no known large matrices with bounded restricted isometry constants, but many random matrices have been shown to remain bounded. The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices. Web forms to evaluate bounds for the Gaussian ensemble are available at the Edinburgh Compressed Sensing RIC page.
Definition
Let A be an m × p matrix and let s < p be an integer. Suppose that there exists a constant such that, for every m × s submatrix As of A and for every vector y,Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant
.