Lp quasi-norm minimization: algorithm and applications

Omar M. Sleem, M. E. Ashour, N. S. Aybat, Constantino M. Lagoa

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Sparsity finds applications in diverse areas such as statistics, machine learning, and signal processing. Computations over sparse structures are less complex compared to their dense counterparts and need less storage. This paper proposes a heuristic method for retrieving sparse approximate solutions of optimization problems via minimizing the ℓp quasi-norm, where 0<p<1. An iterative two-block algorithm for minimizing the ℓp quasi-norm subject to convex constraints is proposed. The proposed algorithm requires solving for the roots of a scalar degree polynomial as opposed to applying a soft thresholding operator in the case of ℓ1 norm minimization. The algorithm’s merit relies on its ability to solve the ℓp quasi-norm minimization subject to any convex constraints set. For the specific case of constraints defined by differentiable functions with Lipschitz continuous gradient, a second, faster algorithm is proposed. Using a proximal gradient step, we mitigate the convex projection step and hence enhance the algorithm’s speed while proving its convergence. We present various applications where the proposed algorithm excels, namely, sparse signal reconstruction, system identification, and matrix completion. The results demonstrate the significant gains obtained by the proposed algorithm compared to other ℓp quasi-norm based methods presented in previous literature.

Original languageEnglish (US)
Article number22
JournalEurasip Journal on Advances in Signal Processing
Issue number1
StatePublished - Dec 2024

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this