Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach

2018/02/20 by Ming Yu, Varun Gupta, Yu, Ming +3 · 3 citations
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #stat.ML

paper · pdf · doi:10.48550/arxiv.1802.06967

openalex publication_date 2018/02/20 · openalex created_date 2018/03/06 · arxiv created 2019/04/10 · arxiv updated 2019/04/11 · openalex updated_date 2026/07/28

Abstract

We study the problem of recovery of matrices that are simultaneously low rank and row and/or column sparse. Such matrices appear in recent applications in cognitive neuroscience, imaging, computer vision, macroeconomics, and genetics. We propose a GDT (Gradient Descent with hard Thresholding) algorithm to efficiently recover matrices with such structure, by minimizing a bi-convex function over a nonconvex set of constraints. We show linear convergence of the iterates obtained by GDT to a region within statistical error of an optimal solution. As an application of our method, we consider multi-task learning problems and show that the statistical error rate obtained by GDT is near optimal compared to minimax rate. Experiments demonstrate competitive performance and much faster running speed compared to existing methods, on both simulations and real data sets.

Citations

• Matrix Factorization Techniques for Recommender Systems
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Local Minima and Convergence in Low-Rank Semidefinite Programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Robust principal component analysis?
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion

Cited by

• High-dimensional low-rank matrix regression with unknown latent structures
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery

Related

• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence