2017

Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications

Haeffele, Benjamin D., Vidal, Rene

Understand

Recently, 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.

Built on

——, “Learning the parts of objects by non-negative matrix factorization,” Nature , vol. 401, no. 6755, pp. 788–791, 1999
1999
Earlier work this paper cites.
D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in Neural Information Processing Systems , 2001, pp. 556–562
2001
Earlier work this paper cites.
R. A. Ryan, Introduction to Tensor Products of Banach Spaces . Springer, 2002
2002
Earlier work this paper cites.
C. Stosiek, O. Garaschuk, K. Holthoff, and A. Konnerth, “In vivo two-photon calcium imaging of neuronal networks,” Proceedings of the National Academy of Sciences of the United States of America , vol. 100, no. 12, pp. 7319–7324, 2003
2003
Earlier work this paper cites.
N. Srebro, J. D. Rennie, and T. S. Jaakkola, “Maximum-margin matrix factorization.” in Neural Information Processing Systems , vol. 17, 2004, pp. 1329–1336
2004
Earlier work this paper cites.
S. Boyd and L. Vandenberghe, Convex Optimization . Cambridge University Press, 2004
2004
Earlier work this paper cites.
S. Burer and R. D. C. Monteiro, “Local minima and convergence in low-rank semidefinite programming,” Mathematical Programming , vol. Series A, no. 103, pp. 427—444, 2005
2005
Earlier work this paper cites.
M. Aharon, M. Elad, and A. M. Bruckstein, “K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation,” IEEE Transactions on Signal Processing , vol. 54, no. 11, pp. 4311–4322, 2006
2006
Earlier work this paper cites.
H. Zou, T. Hastie, and R. Tibshirani, “Sparse principal component analysis,” Journal of Computational and Graphical Statistics , vol. 15, no. 2, pp. 265–286, 2006
2006
Earlier work this paper cites.
A. d’Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. Lanckriet, “A direct formulation for sparse pca using semidefinite programming,” SIAM Review , vol. 49, no. 3, pp. 434–448, 2007
2007
Earlier work this paper cites.
J.-F. Cai, E. J. Candés, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” SIAM Journal of Optimization , vol. 20, no. 4, pp. 1956–1982, 2008
2008
Earlier work this paper cites.
F. Bach, J. Mairal, and J. Ponce, “Convex sparse matrix factorizations,” arXiv:0812.1869v1 , 2008
Original
2008
Earlier work this paper cites.

Similar

N. Spruston, “Pyramidal neurons: dendritic structure and synaptic integration,” Nature Reviews Neuroscience , vol. 9, no. 3, pp. 206–221, 2008
2008
Cited alongside, same era.
J. Mairal, J. Ponce, G. Sapiro, A. Zisserman, and F. R. Bach, “Supervised dictionary learning,” in Neural Information Processing Systems , 2009, pp. 1033–1040
2009
Cited alongside, same era.
A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences , vol. 2, no. 1, pp. 183–202, 2009
2009
Cited alongside, same era.
J. Romberg, “Compressive sensing by random convolution,” SIAM J. Img. Sci. , vol. 2, no. 4, pp. 1098–1128, Nov. 2009
2009
Cited alongside, same era.
J. Mairal, F. Bach, J. Ponce, and G. Sapiro, “Online learning for matrix factorization and sparse coding,” The Journal of Machine Learning Research , vol. 11, pp. 19–60, 2010
2010
Cited alongside, same era.
B. Recht, M. Fazel, and P. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM Review , vol. 52, no. 3, pp. 471–501, 2010
2010
Cited alongside, same era.
J. M. Hendrickx and A. Olshevsky, “Matrix p p -norms are NP-hard to approximate if p ≠ 1 , 2 , ∞ p\neq 1,2,\infty ,” SIAM Journal on Matrix Analysis and Applications , vol. 31, no. 5, pp. 2802–2812, 2010
2010
Cited alongside, same era.
J. T. Vogelstein, A. M. Packer, T. A. Machado, T. Sippy, B. Babadi, R. Yuste, and L. Paninski, “Fast nonnegative deconvolution for spike train inference from population calcium imaging,” Journal of Neurophysiology , vol. 104, no. 6, pp. 3691–3704, 2010
2010
Cited alongside, same era.
Z. Jiang, Z. Lin, and L. S. Davis, “Learning a discriminative dictionary for sparse coding via label consistent k-svd,” in IEEE Conference on Computer Vision and Pattern Recognition , 2011, pp. 1697–1704
2011
Cited alongside, same era.
E. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?” Journal of the ACM , vol. 58, no. 3, 2011
2011
Cited alongside, same era.
H. Birkholz, “A unifying approach to isotropic and anisotropic total variation denoising models,” Journal of Computational and Applied Mathematics , vol. 235, pp. 2502–2514, 2011
2011
Cited alongside, same era.
P. L. Combettes and J. C. Pesquet, “Proximal splitting methods in signal processing,” in Fixed-Point Algorithms for Inverse Problems in Science and Engineering . Springer-Verlag, 2011, vol. 49, pp. 185–212
2011
Cited alongside, same era.

Then

R. J. Tibshirani and J. Taylor, “The solution path of the generalized lasso,” Annals of Statistics , vol. 39, no. 3, pp. 1335–1371, 2011
2011
Later among the works it cites.
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, “The convex geometry of linear inverse problems,” Foundations of Computational Mathematics , vol. 12, no. 6, pp. 805–849, 2012
2012
Later among the works it cites.
J. Akerboom, T.-W. Chen, T. J. Wardill, L. Tian, J. S. Marvin, S. Mutlu, ⋯ \cdots , and L. L. Looger, “Optimization of a GCaMP calcium indicator for neural activity imaging,” The Journal of Neuroscience , vol. 32, pp. 13 819–13 840, 2012
2012
Later among the works it cites.
M. Golbabaee and P. Vandergheynst, “Joint trace/tv minimization: A new efficient approach for spectral compressive imaging,” in IEEE Internation Conference on Image Processing , 2012, pp. 933–936
2012
Later among the works it cites.
F. Bach, “Convex relaxations of structured matrix factorizations,” arXiv:1309.3117v1 , 2013
Original
2013
Later among the works it cites.
R. Cabral, F. De la Torre, J. P. Costeira, and A. Bernardino, “Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition,” in IEEE International Conference on Computer Vision , 2013, pp. 2488–2495
2013
Later among the works it cites.
Y. Xu and W. Yin, “A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion,” SIAM Journal on Imaging Sciences , vol. 6, no. 3, pp. 1758–1789, 2013
2013
Later among the works it cites.
E. A. Pnevmatikakis, T. A. Machado, L. Grosenick, B. Poole, J. T. Vogelstein, and L. Paninski, “Rank-penalized nonnegative spatiotemporal deconvolution and demixing of calcium imaging data,” Abstract: Computational and Systems Neuroscience (Cosyne), 2013
2013
Later among the works it cites.
H. Zhang, W. He, L. Zhang, H. Shen, and Q. Yuan, “Hyperspectral image restoration using low-rank matrix recovery,” IEEE Trans. on Geoscience and Remote Sensing , vol. PP, pp. 1–15, 2013
2013
Later among the works it cites.
Y. Yu, X. Zhang, and D. Schuurmans, “Generalized conditional gradient for sparse estimation,” arXiv preprint arXiv:1410.4828 , 2014
Original
2014
Later among the works it cites.
E. Richard, G. R. Obozinski, and J.-P. Vert, “Tight convex relaxations for sparse matrix factorization,” in Neural Information Processing Systems , 2014, pp. 3284–3292
2014
Later among the works it cites.
B. Haeffele, E. Young, and R. Vidal, “Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing,” in International Conference on Machine Learning , 2014, pp. 2007–2015
2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…