Patent ID: 8219360

Claim:
A method for reconstructing a signal x from sign measurements y, wherein {circumflex over (x)} l is a current estimate of the reconstructed signal x, comprising for each iteration l, until the current estimate convergences with a previous estimate {circumflex over (x)} l−1 , the steps of: estimating measurements {tilde over (y)} using the previous estimate {circumflex over (x)} l−1 and a measurement matrix Φ according to {tilde over (y)} l =Φ{circumflex over (x)} l−1 ; identifying, in a vector r, sign measurements y that have signs inconsistent with the estimated measurements {tilde over (y)}; determining a correction signal according to s=Φ T r l ; identifying a support set T l for the correction signal s according to T l =supp( s l | 2K ) U supp( {circumflex over (x)} l−1 ), where supp(.) determines the support set T l , and (.)| 2K selects 2K components of the signal x with largest magnitudes, and setting all other components of the signal x to 0; performing consistent reconstruction according to b l | T =arg min x ∥Φx∥ 2 2 , such that ∥x∥2=1, and x| Tc =0, wherein | T denotes elements in the support set and | Tc denotes elements not in the support set; and updating the current estimate {circumflex over (x)} l , wherein the estimating, identifying, determining, identifying, performing, and updating steps are performed in a computer system, wherein the steps are performed in a processor.