Instanceoptimality in probability with an ℓ1 minimization decoder
 Citation data:

Applied and Computational Harmonic Analysis, ISSN: 10635203, Vol: 27, Issue: 3, Page: 275288
 Publication Year:
 2009
 Repository URL:
 http://scholars.library.tamu.edu/vivo/display/n221377SE; http://hdl.handle.net/10754/598633
 DOI:
 10.1016/j.acha.2009.05.001
 Author(s):
 Publisher(s):
 Tags:
 Mathematics; ℓ1minimization decoder; Compressed sensing; Instanceoptimality in probability
article description
Let Φ(ω), ω∈Ω, be a family of n×N random matrices whose entries ϕi,j are independent realizations of a symmetric, real random variable η with expectation Eη=0 and variance Eη2=1/n. Such matrices are used in compressed sensing to encode a vector x∈RN by y=Φx. The information y holds about x is extracted by using a decoder Δ:Rn→RN. The most prominent decoder is the ℓ1 minimization decoder Δ which gives for a given y∈Rn the element Δ(y)∈RN which has minimal ℓ1 norm among all z∈RN with Φz=y. This paper is interested in properties of the random family Φ(ω) which guarantee that the vector x¯:=Δ(Φx) will with high probability approximate x in ℓ2N to an accuracy comparable with the best k term error of approximation in ℓ2N for the range k⩽an/log2(N/n). This means that for the above range of k, for each signal x∈RN, the vector x¯:=Δ(Φx) satisfies ‖x−x¯‖ℓ2N⩽Cinfz∈Σk‖x−z‖ℓ2N with high probability on the draw of Φ. Here, Σk consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math., in press] who showed this property when η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where η is the Bernoulli random variable which takes the values ±1/n with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [A. Litvak, A. Pajor, M. Rudelson, N. TomczakJaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005) 491–523].