Least Sparsity of p-Norm Based Optimization Problems with p>1*

Abstract

Motivated by lp-optimization arising from sparse optimization, high-dimensional data analytics and statistics, this paper studies sparse properties of a wide range of p-norm based optimization problems with p > 1, including generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. It is well known that when p > 1, these optimization problems lead to less sparse solutions. However, the quantitative characterization of the adverse sparse properties is not available. This paper shows how to exploit optimization and matrix analysis techniques to develop a systematic treatment of a broad class of p-norm based optimization problems for a general p > 1 and show that their optimal solutions attain full support, and thus have the least sparsity, for almost all measurement matrices and measurement vectors. Comparison to lp-optimization with 0 < p <=1 and implications for robustness as well as extensions to the complex setting are also given. These results shed light on analysis and computation of general p-norm based optimization problems in various applications.