Estimation of Simultaneously Sparse and Low Rank Matrices
This addresses matrix estimation for structured data like graphs, but it appears incremental as it builds on existing penalization methods.
The paper tackles the problem of estimating matrices that are both sparse and low-rank, common in social networks or protein interactions, by introducing a convex mixed penalty combining $\ell_1$-norm and trace norm, and it provides an oracle inequality and generalization error bounds for link prediction.
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.