# Least Sparsity of p-norm based Optimization Problems with p > 1

arXiv: https://arxiv.org/abs/1708.06055 · HTML: https://mlsanity.com/paper/1708.06055/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2017.

## Built on by (most cited first, 3 of 3)

- [Sparse Universum Quadratic Surface Support Vector Machine Models for Binary Classification](https://mlsanity.com/paper/2104.01331/) (2021)
- [Error-Correction for Sparse Support Recovery Algorithms](https://mlsanity.com/paper/2103.03801/) (2021)
- [L0-Regularized Quadratic Surface Support Vector Machines](https://mlsanity.com/paper/2501.11268/) (2025)

## Abstract (arXiv)

Motivated by ℓp-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. In this paper, by exploiting optimization and matrix analysis techniques, we give a systematic treatment of a broad class of p-norm based optimization problems for a general p > 1 and show that optimal solutions to these problems attain full support, and thus have the least sparsity, for almost all measurement matrices and measurement vectors. Comparison to ℓp-optimization with 0 < p ≤ 1 and implications to robustness are also given. These results shed light on analysis and computation of general p-norm based optimization problems in various applications.