A strong restricted isometry property, with an application to phaseless compressed sensing

The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if A is an element of R-mxn satisfies SRIP and phaseless measurements vertical bar Ax(0)vertical bar = b are observed about a k-sparse signal x(0) is an element of R-n, then minimizing the l(1) norm subject to vertical bar Ax vertical bar = b recovers x(0) up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from O(k log(en/k)) measurements with these matrices via l(1) minimization over vertical bar Ax vertical bar = b. Our analysis also yields an erasure robust version of the Johnson Lindenstrauss Lemma. (C) 2015 Elsevier Inc. All rights reserved.