Sparse Recovery from Inaccurate Saturated Measurements
- PDF / 992,970 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 188 Views
Sparse Recovery from Inaccurate Saturated Measurements Simon Foucart1 · Jiangyuan Li1
Received: 1 September 2017 / Accepted: 8 March 2018 © Springer Science+Business Media B.V., part of Springer Nature 2018
Abstract This article studies a variation of the standard compressive sensing problem, in which sparse vectors x ∈ RN are acquired through inaccurate saturated measurements y = S (Ax + e) ∈ Rm , m N . The saturation function S acts componentwise by sending entries that are large in absolute value to plus-or-minus a threshold while keeping the other entries unchanged. The present study focuses on the effect of the presaturation error e ∈ Rm . The existing theory for accurate saturated measurements, i.e., the case e = 0, which exhibits two regimes depending on the magnitude of x ∈ RN , is extended here. A recovery procedure based on convex optimization is proposed and shown to be robust to presaturation error in both regimes. Another procedure ignoring the presaturation error is also analyzed and shown to be robust in the small magnitude regime. Keywords Compressive sensing · Saturation · Convex programming Mathematics Subject Classification 94A12 · 90C05 · 60D05
1 Introduction Suppose that vectors x ∈ RN are acquired through m linear measurements yi = ai , x = N a i x, i = 1, . . . , m, for some a1 , . . . , am ∈ R . In condensed form, this reads y = Ax, where m×N has rows a1 , . . . , am . When m is smaller than N , it is in general the matrix A ∈ R inconceivable to recover x ∈ RN from the mere knowledge of y ∈ Rm , but the theory of compressive sensing [3, 5, 8] made it clear that such a recovery task is in fact possible when some prior information about the structure of x is available. Typically, it is assumed that the vectors of interest are s-sparse, i.e., that the x ∈ RN possess at most s nonzero entries. This work is the result of Jiangyuan Li’s capstone project, carried out at Texas A&M University as part of an exchange with Beihang University. S. Foucart is partially supported by the NSF under the grant DMS-1622134.
B S. Foucart
[email protected]
1
Texas A&M University, College Station, USA
S. Foucart, J. Li
In this case, it is now well known that only m s ln(eN/s) random measurements enable the exact recovery of all s-sparse vectors x ∈ RN via various efficient algorithms taking the compressed version y = Ax ∈ Rm as an input (together with the matrix A itself, of course). Now suppose that sparse vectors x ∈ RN are not acquired through y = Ax but rather through S (y) = S (Ax), where S = Sμ is the saturation function depicted below.
⎧ ⎨ −μ, t ∈ (−∞, −μ], t ∈ (−μ, +μ), S (t) = t, ⎩ +μ, t ∈ [+μ, +∞).
Intuitively, at one extreme, when the threshold μ is very large (compared to the magnitude of x), the saturation function S has no effect and the setting of standard compressive sensing prevails, so one expects exact recovery of x to be possible. At the other extreme, when the threshold μ is very small (compared to the magnitude of x), knowing S (y) reduces to knowing the bina
Data Loading...
