Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications
- 19 February 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 42 (6) , 1468-1482
Abstract
Convex formulations of low-rank matrix factorization problems have received considerable attention in machine learning. However, such formulations often require solving for a matrix of the size of the data matrix, making it challenging to apply them to large scale datasets. Moreover, in many applications the data can display structures beyond simply being low-rank, e.g., images and videos present complex spatio-temporal structures that are largely ignored by standard low-rank methods. In this paper we study a matrix factorization technique that is suitable for large datasets and captures additional structure in the factors by using a particular form of regularization that includes well-known regularizers such as total variation and the nuclear norm as particular cases. Although the resulting optimization problem is non-convex, we show that if the size of the factors is large enough, under certain conditions, any local minimizer for the factors yields a global minimizer. A few practical algorithms are also provided to solve the matrix factorization problem, and bounds on the distance from a given approximate solution of the optimization problem to the global optimum are derived. Examples in neural calcium imaging video segmentation and hyperspectral compressed recovery show the advantages of our approach on high-dimensional datasets.Keywords
Funding Information
- NSF (1447822, 1618485, 1618637)
- IARPA DIVA (D17PC00345)
This publication has 26 references indexed in Scilit:
- Optimization of a GCaMP Calcium Indicator for Neural Activity ImagingThe Journal of Neuroscience, 2012
- The solution path of the generalized lassoThe Annals of Statistics, 2011
- Robust principal component analysis?Journal of the ACM, 2011
- A unifying approach to isotropic and anisotropic total variation denoising modelsJournal of Computational and Applied Mathematics, 2011
- Fast Nonnegative Deconvolution for Spike Train Inference From Population Calcium ImagingJournal of Neurophysiology, 2010
- Matrix p-Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$SIAM Journal on Matrix Analysis and Applications, 2010
- Pyramidal neurons: dendritic structure and synaptic integrationNature Reviews Neuroscience, 2008
- $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse RepresentationIEEE Transactions on Signal Processing, 2006
- Sparse Principal Component AnalysisJournal of Computational and Graphical Statistics, 2006
- Local Minima and Convergence in Low-Rank Semidefinite ProgrammingMathematical Programming, 2004