Sparse signal recovery and dynamic update of the underdetermined system

Sparse signal priors help in a variety of modern signal processing tasks. In many cases, a sparse signal needs to be recovered from an underdetermined system of equations. For instance, sparse approximation of a signal with an overcomplete dictionary or reconstruction of a sparse signal from a small number of linear measurements. The reconstruction problem typically requires solving an ℓ₁ norm minimization problem. In this paper we present homotopy based algorithms to update the solution of some ℓ₁ problems when the system is updated by adding new rows or columns to the underlying system matrix. We also discuss a case where these ideas can be extended to accommodate for more general changes in the system matrix.