chapter  9
22 Pages

Quadratic Basis Pursuit

WithHenrik Ohlsson, Allen Y. Yang, Roy Dong, Michel Verhaegen, S. Shankar Sastry

Henrik Ohlsson Department of Electrical Engineering and Computer Sciences, University of California, Berkeley

Allen Y. Yang Department of Electrical Engineering and Computer Sciences, University of California, Berkeley

Roy Dong Department of Electrical Engineering and Computer Sciences, University of California, Berkeley

Michel Verhaegen Delft Center for Systems and Control, Delft University

S. Shankar Sastry Department of Electrical Engineering and Computer Sciences, University of California, Berkeley

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 9.1.1 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 9.1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

9.2 Quadratic Basis Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9.2.1 Convex Relaxation via Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9.2.2 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

9.3 Numerical Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 9.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

9.4.1 Nonlinear Compressive Sensing in Real Domain . . . . . . . . 206 9.4.2 The Shepp-Logan Phantom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 9.4.3 Subwavelength Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

9.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Vector

9.1 Introduction Consider the problem of finding the sparsest signal x satisfying a system

of linear equations:

‖x‖0 subj. to yi = bTi x, yi ∈ <, bi ∈ <n, i = 1, . . . , N.