Methods for sparse and low-rank recovery under simplex constraints

DOI10.5705/SS.202016.0220MaRDI QIDQ5109909zbMATH OpenOpenAlexWikidataFDO

Authors Ping Li, Syama Sundar Rangapuram, Martin Slawski

Publication date 14 May 2020

Published in STATISTICA SINICA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00507

zbMATH Keywords

D.C. programmingdensity matrices of quantum systemsestimation of mixture proportionssimplex constraintssparsity

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Applications of statistics to physics (62P35)

Abstract: The de-facto standard approach of promoting sparsity by means of $el{l}_1$-regularization becomes ineffective in the presence of simplex constraints, i.e.,~the target is known to have non-negative entries summing up to a given constant. The situation is analogous for the use of nuclear norm regularization for low-rank recovery of Hermitian positive semidefinite matrices with given trace. In the present paper, we discuss several strategies to deal with this situation, from simple to more complex. As a starting point, we consider empirical risk minimization (ERM). It follows from existing theory that ERM enjoys better theoretical properties w.r.t.~prediction and $el{l}_2$-estimation error than $el{l}_1$-regularization. In light of this, we argue that ERM combined with a subsequent sparsification step like thresholding is superior to the heuristic of using $el{l}_1$-regularization after dropping the sum constraint and subsequent normalization. At the next level, we show that any sparsity-promoting regularizer under simplex constraints cannot be convex. A novel sparsity-promoting regularization scheme based on the inverse or negative of the squared $el{l}_2$-norm is proposed, which avoids shortcomings of various alternative methods from the literature. Our approach naturally extends to Hermitian positive semidefinite matrices with given trace. Numerical studies concerning compressed sensing, sparse mixture density estimation, portfolio optimization and quantum state tomography are used to illustrate the key points of the paper.

Recommendations

• The convex geometry of linear inverse problems
• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• Stable Recovery of Sparse Signals Via Regularized Minimization
• Convex relaxation algorithm for a structured simultaneous low-rank and sparse recovery problem
• Sparse trace norm regularization

Cited in

(17)

• DC programming and DCA: thirty years of developments
• Low-rank and sparse matrix recovery via inexact Newton-like method with non-monotone search
• Hyper-sparsity in the revised simplex method and how to exploit it
• Nomonotone spectral gradient method for sparse recovery
• Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization
• Sparse Recovery With Graph Constraints
• scientific article; zbMATH DE number 5853153 (Why is no real title available?)
• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• Recovery of Short, Complex Linear Combinations Via<tex>$ell _1$</tex>Minimization
• Recovery Algorithms for Vector-Valued Data with Joint Sparsity Constraints
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values
• A general theory for subspace-sparse recovery
• A Fast Majorize–Minimize Algorithm for the Recovery of Sparse and Low-Rank Matrices
• Sparse recovery under nonnegativity and sum-to-one constraints
• A new generalized shrinkage conjugate gradient method for sparse recovery
• Simplex constrained sparse optimization via tail screening
• Rank related properties for basis pursuit and total variation regularization

This page was built for publication: Methods for sparse and low-rank recovery under simplex constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5109909)