The Restricted Isometry Property 1.1 2007/07/16 12:20:42.648 GMT-5 2007/09/21 23:19:13.692 GMT-5 Ronald A. DeVore devore@math.sc.edu Elchin Asgarov deoxman@gmail.com Raymond Wagner rwagner@rice.edu Richard G. Baraniuk richb@rice.edu Ronald A. DeVore devore@math.sc.edu Chinmay Hegde ch3@rice.edu Mark Davenport md@rice.edu We say that an n×Nn times N matrix ΦΦ has the restricted isometry property (RIP) for kk if for each T⊆{1,…,N}T subseteq { lbrace {1 , dotslow , N} rbrace} such that #T≤kitalic "#" T <= k , ΦTΦ_T (the matrix formed by choosing the columns of ΦΦ whose indices are in TT ) has the property ( 1 − δ k ) ∥ x T ∥ ℓ 2 ≤ ∥ Φ T ( x ) ∥ ℓ 2 ≤ ( 1 + δ k ) ∥ x T ∥ ℓ 2 (RIP) where 0<δk<10 <δ_k <1 . This useful definition is by Candes and Tao. The idea is that the embedding of a kk -dimensional space in MM -dimensional space almost preserves norm – like an isometry. Another way of looking at it is to consider the matrix ΦTtΦTΦ_T^t Φ_T , of size k×kk times k . This matrix is symmetric, positive definite, and it’s eigen-values are between 1−δk1 - δ_k and 1+δk1 +δ_k . I prefer the following modified condition (dubbed the MIRP), which is more convenient for mathematical analysis: ( c 1 ) − 1 ∥ x T ∥ ℓ 2 ≤ ∥ Φ T ( x ) ∥ ℓ 2 ≤ c 1 ∥ x T ∥ ℓ 2 (MRIP) We can now state the following theorem. If ΦΦ satisfies MRIP for 2k2 k then ∃Δ exists Δ s.t. (Φ,Δ) \( {Φ , Δ} \) is instance optimal for ℓ1Nℓ_1^N for KK . This shows that whenever we have a matrix ΦΦ satisfying the MRIP for 2k2 k then it will perform well on encoding vectors (at least in the sense of ℓ1Nℓ_1^N accuracy). The question is how can we construct measurement matrices with this property? We can construct ΦΦ using Gaussian entries and then normalizing the columns. ∃ exists constant c>0c >0 s.t. if k≤cnlog(N∕n)k <= c n over {l { \( {N ∕ n} \)}} then with high probability ΦΦ satisfies RIP and MRIP for kk . Given NN and nn , the range of kk in the above results reflects how accurately we can recover data. There is another constant c′c^′ that serves as a converse bound for Theorem 3. This converse can be derived using Gluskin widths. The following generic problem is of great interest: Consider the class of matrices ℳ = { Φ M × N , Φ has some prescribed property(eg. Toeplitz, circulant, etc.) } . What is the largest kk for which such a matrix can have the MRIP.