Probing the Pareto Frontier for Basis Pursuit Solutions

• DOI: 10.1137/080714488
• Publication Date: 2008-11-26T23:12:26Z
• Authors: Ewout van den Berg; Michael P. Friedl...
• Keywords: Least-squares function approximation; Underdetermined system; Basis pursuit; Basis function

The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis denoise (BPDN) fits the only approximately, and single parameter determines curve that traces optimal trade-off between fit solution. We prove this is convex continuously differentiable over all points interest, show it gives explicit relationship to two other optimization problems closely related BPDN. describe root-finding algorithm for finding arbitrary on curve; suitable are large scale those in complex domain. At each iteration, spectral gradient-projection method approximately minimizes with constraint. Only matrix-vector operations required. primal-dual function derivative information needed method. Numerical experiments comprehensive set test demonstrate scales well problems.