The Nullspace Property 1.1 2007/07/16 12:20:42.648 GMT-5 2007/09/21 23:18:07.577 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 begin with a property of the null space NN which is at the heart of proving results on instance-optimality. We say that NN has the Null Space Property if for all η∈Nη in N and all TT with #T≤kitalic "#" T <= k we have ∥ η ∥ X ≤ c 1 ∥ η T C ∥ X Intuitively, NSP implies that for any vector in the nullspace the energy will not be concentrated in a small number of entries. The following are equivalent formulations for NSP XX for kk : ∥η∥X≤c1⁢σk⁢(η) ∥ η T ∥ X ≤ c 1 ′ ⁢ ∥ η T C ∥ X where η = η T + η T C . Note also that the triangle inequality can be used as follows ∥ η ∥ X = ∥ η T + η T C ∥ X ≤ ∥ η T ∥ X + ∥ η T C ∥ X which shows that (b) is equivalent to NSP. If (Φ,Δ) \( {Φ , Δ} \) is instance optimal on XX for the value kk , then ΦΦ satisfies the NSP for 2k2 k on XX with an equivalent constant. If ΦΦ has the NSP for XX and 2k2 k then ∃Δ exists Δ s.t. ΦΦ has the instance optimal property for kk . We will prove a slightly weaker version of this to save time. We first prove that instance optimality for kk implies NSP XX for kk (hence this is slightly weaker than advertised) . Let η∈Nη in N and set z=Δ(0)z =Δ { \( 0 \)} then ∥ η − z ∥ ≤ c 0 σ k ( η ) ∥ η + z ∥ ≤ c 0 σ k ( η )   ∥ η ∥ ≤ max ⁡ { ∥ η − z ∥ , ∥ η + z ∥ } ≤ c 0 σ k ( η ) instance optimal property − z ∈ N triangle inequality We now prove 2. Suppose ΦΦ has the NSP for 2k2 k . Given yy , ℱℱ(y)={x:Φ(x)=y}{ \( y \)} ={ lbrace {x : Φ { \( x \)} = y} rbrace}. Let us define the decoder ΔΔ by Δ ( y ) : = arg ⁡ min ⁡ { σ K ( x ) X : x ∈ ℱ ( y ) } , then ∥ x − Δ ( Φ ( x ) ) ∥ X = ∥ x − x ′ ∥ X ≤ c 1 σ 2 K ( x − x ′ ) ≤ c 1 ( σ K ( x ) − σ K ( x ′ ) ) specific 2K term approximation ≤ 2 c 1 σ K ( x ) QED. Note that the instance optimal property automatically gives reproduction of KK -sparse signals. At this stage the challenge is to create ΦΦ with this instance optimal property. For this we shall use the restricted isometry property as introduced earlier and which we now recall.