Quadratic Basis Pursuit

Y ang, Member, IEEE, Roy Dong, Michel V erhaegen, S. Shankar Sastry, Fellow, IEEE Abstract--In many compressive sensing problems today, the relationship between the measurements and the unknowns could be nonlinear . Traditional treatment of such nonlinear relationships have been to approximate the nonlinearity via a linear model and the subsequent un-modeled dynamics as noise. The ability to more accurately characterize nonlinear models has the potential to improve the results in both existing compressive sensing applications and those where a linear approximation does not suffice, e.g., phase retrieval. In this paper, we extend the classical compressive sensing framework to a second-order T aylor expansion of the nonlinearity. Using a lifting technique and a method we call quadratic basis pursuit, we show that the sparse signal can be recovered exactly when the sampling rate is sufficiently high. We further present efficient numerical algorithms to recover sparse signals in second-order nonlinear systems, which are considerably more difficult to solve than their linear counterparts in sparse optimization. I NTRODUCTION Consider the problem of finding the sparsest signalx satisfying a system of linear equations: min x R n ‖ x ‖ 0 subj. One of the most well known approaches is to relax the zero norm and replace it with the 1-norm: min x R n ‖ x ‖ 1 subj. The ability to recover the optimal solution to (1) is essential in the theory of compressive sensing (CS) [4], [5] and a tremendous amount of work has been dedicated to solving and analyzing the solution of (1) and (2) in the last decade. Today CS is regarded as a powerful tool in signal processing and widely used in many applications. For a detailed review of the literature, the reader is referred to several recent publications such as [6], [7].