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

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.

References in corpus (31)

• Natural Language Processing (almost) from Scratch
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Fast non-negative deconvolution for spike train inference from population calcium imaging
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Support union recovery in high-dimensional multivariate regression
• Estimation of high-dimensional low-rank matrices
• Guaranteed Matrix Completion via Non-convex Factorization
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Incoherence-Optimal Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• Estimation of Simultaneously Sparse and Low Rank Matrices
• The Landscape of Empirical Risk for Non-convex Losses
• Fast matrix completion without the condition number
• A structured matrix factorization framework for large scale calcium imaging data analysis
• Union Support Recovery in Multi-task Learning
• Computational Limits for Matrix Completion
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Distributed Multi-Task Learning with Shared Representation
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Adaptive Estimation in Two-way Sparse Reduced-rank Regression
• Alternating minimization and alternating descent over nonconvex sets
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Scalable Interpretable Multi-Response Regression via SEED
• Multitask Learning using Task Clustering with Applications to Predictive Modeling and GWAS of Plant Varieties

Cited by in corpus (5)

• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• Extraction of hierarchical functional connectivity components in human brain using resting-state fMRI
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Simultaneous Parameter Learning and Bi-Clustering for Multi-Response Models