A collection of fixed-rank algorithms

List of fixed-rank geometries and algorithms

Optimization on the set of fixed-rank matrices and tensors have seen numerous contributions over the past few years. The driving force has been applications like low-rank matrix/tensor completion, multiclass classification, distance matrix completion problems, to name a few. This requires descriptions of the search space of fixed-rank matrices/tensors directed toward optimization.

This webpage lists the geometries that have been proposed, including specific optimization algorithms.

If you find any omission or you would like to add your codes/work on this page, please do let me know at bamdevm@gmail.com.

The list is outdated as of 2018.

• • “Low-rank retractions: a survey and new results”, Absil and Oseledets. Computational Optimization and Applications, 2014.
  • “Alternating Least Squares Tensor Completion in The TT-Format”, Grasedyck, Kluge, and Krämer. arXiv:1509.00311, 2015.
  • “Riemannian optimization for high-dimensional tensor completion”, Steinlechner. Technical report, 2015.
  • “Robust Low-Rank Matrix Completion by Riemannian Optimization”, Cambier and Absil. Technical report, 2015 [Codes webpage].
  • “A New Retraction for Accelerating the Riemannian Three-Factor Low-Rank Matrix Completion Algorithm”, Li, Zhao, Lin, and Chang. IEEE CVPR, 2015.
  • “Riemannian preconditioning for tensor completion”, Kasai and Mishra. arXiv:1506.02159, 2015 [Codes webpage].
  • “Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient”, Tan, Xiao, Gao, Xu, Van Den Hengel, and Shi. arXiv:1503.02828, 2015 [Codes].
  • “Optimization on the Hierarchical Tucker manifold – applications to tensor completion”, Da Silva and Herrmann. arXiv:1405.2096, 2014 [HTOpt webpage].
  • “Nuclear Norm Minimization via Active Subspace Selection”, Hsieh and Olsen. ICML, 2014 [Codes].
  • “Low-rank matrix completion via preconditioned optimization on the Grassmann manifold”, Boumal and Absil. Linear Algebra Appl., 2015 [RTRMC with preconditioning code].
  • “Riemannian Pursuit for Big Matrix Recovery”, Tan, Tsang, Wang, Vandereycken and Pan. ICML, 2014 [Code webpage].
  • “Low rank matrix completion by alternating steepest descent methods”, Tanner and Wei. Submitted, 2014 [Codes webpage].
  • “Low-rank tensor completion by Riemannian optimization”, Kressner, Steinlechner and Vandereycken. BIT, 2014 [geomCG code].
  • “Tucker factorization with missing data with application to low-n-rank tensor completion”, Filipović and Jukić. Multidim Syst Sign Process, 2013.
  • “R3MC: A Riemannian three-factor algorithm for low-rank matrix completion”, Mishra and Sepulchre. arXiv, 2012 [R3MC-code].
  • “Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm”, Wen, Yin and Zhang. Math. Prog. Comp., 2012 [LMaFit-code].
  • “A Riemannian geometry for low-rank matrix completion”, Mishra, Adithya Apuroop and Sepulchre. arXiv, 2012 [qGeomMC-code].
  • “Scaled Gradients on Grassmann Manifolds for Matrix Completion”, Ngo and Saad. NIPS, 2012 [ScGrassMC-code].
  • “Fixed-rank matrix factorizations and Riemannian low-rank optimization”, Mishra, Meyer, Bonnabel and Sepulchre. arXiv, 2012.
  • “Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries”, Absil, Amodei and Meyer. 2012.
  • “A Riemannian geometry with complete geodesics for the set of positive semidefinite matrices of fixed rank”, Vandereycken, Absil and Vandewalle. IMA J. Numerical Analysis, 2012.
  • “Low-rank matrix completion by Riemannian optimization”, Vandereycken. SIOPT, 2013 [LRGeom-code].
  • “Online Learning in the Embedded Manifold of Low-rank Matrices”, Shalit, Weinshall and Chechik. JMLR, 2012.
  • “Low-rank optimization with trace norm penalty”, Mishra, Meyer, Bach and Sepulchre. arXiv, 2011 [Tracenorm-code].
  • “RTRMC : A Riemannian Trust-Region method for low-rank Matrix Completion”, Boumal and Absil. NIPS, 2012 [RTRMC-code].
  • “Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion”, Dai, Milenkovic and Kerman. IEEE TSS, 2011 [SET-code].
  • “Linear Regression under Fixed-Rank Constraints: A Riemannian Approach”, Meyer, Bonnabel and Sepulchre. ICML, 2011.
  • “Regression on Fixed-Rank Positive Semidefinite Matrices: A Riemannian Approach”, Meyer, Bonnabel and Sepulchre. JMLR, 201.
  • “A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations”, Vandereycken and Vandewalle. SIMAX, 2010.
  • “Low-Rank Optimization on the Cone of Positive Semidefinite Matrices”, Journée, Bach, Absil and Sepulchre. SIOPT, 2010 [Code].
  • “Online Learning in the Manifold of Low-Rank Matrices”, Shalit, Weinshall and Chechik. NIPS, 2010 [Loreta-code].
  • “Grassmann algorithms for low rank approximation of matrices with missing values”, Simonsson and Eldén. BIT Num. Mathematics, 2010.
  • “Online Identification and Tracking of Subspaces from Highly Incomplete Information”, Balzano, Nowak and Recht. arXiv:1006.4046, 2010 [GROUSE-code].
  • “Embedded geometry of the set of symmetric positive semidefinite matrices of fixed rank”, Vandereycken, Absil and Vandewalle. IEEE Workshop on SSP, 2009.
  • “A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion”, Keshavan and Oh. arXiv, 2009 [OptSpace-code].
  • “Geometric distance and mean for positive semi-definite matrices of fixed rank”, Bonnabel and Sepulchre. SIMAX, 2009.
  • “Dynamical Low-Rank Approximation”, Koch and Lubich. SIMAX, 2007.

• “Damped Newton algorithms for matrix factorization with missing data”, Buchanan and Fitzgibbon. CVPR, 2005
• “Maximum-Margin Matrix Factorization”, Srebro, Rennie and Jaakola. NIPS, 2004 [MMMF-code].