Estimation of Simultaneously Sparse and Low Rank Matrices

Abstract

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 ${\ell }_1$-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.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• Model Selection Through Sparse Maximum Likelihood Estimation

Cited by in corpus (22)

• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Simultaneously sparse and low-rank abundance matrix estimation for hyperspectral image unmixing
• Enhanced Low-Rank Matrix Approximation
• Variable Selection and Task Grouping for Multi-Task Learning
• Tight convex relaxations for sparse matrix factorization
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• Community Detection in Partially Observable Social Networks
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Mask-GVAE: Blind Denoising Graphs via Partition
• Link Prediction in Graphs with Autoregressive Features
• Factorization Machines with Regularization for Sparse Feature Interactions
• Three Operator Splitting with a Nonconvex Loss Function
• Soft Tensor Regression
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers
• Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
• Log-Normal Matrix Completion for Large Scale Link Prediction
• Estimation of Shortest Path Covariance Matrices
• DynACPD Embedding Algorithm for Prediction Tasks in Dynamic Networks
• Graph Prediction in a Low-Rank and Autoregressive Setting
• Exact solutions in low-rank approximation with zeros