Estimation of Simultaneously Sparse and Low Rank Matrices

By Pierre-André Savalle, Emile Richard, Nicolas Vayatis. 2012

212 citations recorded by the source corpus.

The paper introduces a penalized matrix estimation procedure aiming at solutions which are sparse and low-rank at the same time. Such structures arise in the context of social networks or protein interactions where underlying graphs have adjacency matrices which are block-diagonal in the appropriate basis. We introduce a convex mixed penalty which involves l1-norm and trace norm simultaneously. We obtain an oracle inequality which indicates how the two effects interact according to the nature of the target matrix. We bound generalization error in the link prediction problem. We also develop proximal descent strategies to solve the optimization problem efficiently and evaluate performance on synthetic and real data sets.

Subfields: Artificial Intelligence, Computational Mechanics, Statistical and Nonlinear Physics, Statistics and Probability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistical and Nonlinear Physics

In Statistics and Probability

In Mathematical Optimization

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “Recovering a matrix that is simultaneously low rank and sparse has applications in problems such as co-variance matrix estimation, graph denoising and link prediction (Richard et al., 2012).”
Learning Social Infectivity in Sparse Low-rank Networks Using Multi-dimensional Hawkes Processes (2013, background): “Furthermore, [14] shows that the accuracy of matrix completion can be improved with both sparsity and low-rank regularizations.”
Compression-aware Training of Deep Networks (2017, methodology): “To learn our model with this new regularizer consisting of two main terms, we make use of the incremental proximal descent approach proposed in [Richard et al., 2012], which has the benefit of having a lower memory footprint than parallel proximal methods.”
Kronecker-Basis-Representation Based Tensor Sparsity and Its Applications to Tensor Recovery (2018, background): “…with matrix low-rankness [16], [22], such as joint trace/TV based MSI recovery [23], [27] and joint low-rank/sparsity based matrix recovery [55], [56], etc. Matrix completion (MC) and matrix-based robust principal component analysis (RPCA) are two of the most typical matrix recovery problems.”
Graph Structure Learning for Robust Graph Neural Networks (2020, methodology): “In particular, the proximal operator of l1 norm and nuclear norm can be represented as [4, 27],”