[en] We consider two Riemannian geometries for the manifold M(p, m × n)
of all m × n matrices of rank p. The geometries are induced on M(p, m × n) by
viewing it as the base manifold of the submersion π : (M, N) → M NT, selecting
an adequate Riemannian metric on the total space, and turning π into a Riemannian
submersion. The theory of Riemannian submersions, an important tool in Riemannian
geometry, makes it possible to obtain expressions for fundamental geometric objects
onM(p, m × n) and to formulate the Riemannian Newton methods onM(p, m × n)
induced by these two geometries. The Riemannian Newton methods admit a stronger
and more streamlined convergence analysis than the Euclidean counterpart, and the
computational overhead due to the Riemannian geometric machinery is shown to be
mild. Potential applications include low-rank matrix completion and other low-rank
matrix approximation problems.
Disciplines :
Computer science
Author, co-author :
Absil, Pierre-Antoine
Amodei, Luca
Meyer, Gilles ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Smart grids
Language :
English
Title :
Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
Publication date :
2014
Journal title :
Computational Statistics
ISSN :
0943-4062
eISSN :
1613-9658
Publisher :
Springer, Germany
Volume :
29
Issue :
3-4
Pages :
569-590
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Abraham R, Marsden JE, Ratiu T (1988) Manifolds, tensor analysis and applications, applied mathematical sciences, vol 75, 2nd edn. Springer, New York.
Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton. http://sites. uclouvain. be/absil/amsbook/.
Absil PA, Baker CG, Gallivan KA (2007) Trust-region methods on Riemannian manifolds. Found Comput Math 7(3): 303-330.
Adler RL, Dedieu JP, Margulies JY, Martens M, Shub M (2002) Newton's method on Riemannian manifolds and a geometric model for the human spine. IMA J Numer Anal 22(3): 359-390.
Amodei L, Dedieu JP, Yakoubsohn JC (2009) A dynamical approach to low-rank approximation of a matrix. In: Communication at the 14th Belgian-French-German conference on optimization, 14-18 September 2009.
Boumal N, Absil PA (2011) RTRMC: a Riemannian trust-region method for low-rank matrix completion. In: Shawe-Taylor J, Zemel R, Bartlett P, Pereira F, Weinberger K (eds) Advances in neural information processing systems 24 (NIPS), pp 406-414, http://perso. uclouvain. be/pa. absil/RTRMC/.
Boumal N, Mishra B (2013) The Manopt toolbox. http://www. manopt. org, version 1. 0. 1.
Dai W, Milenkovic O, Kerman E (2011) Subspace evolution and transfer (set) for low-rank matrix completion. IEEE Trans Signal Process 59(7): 3120-3132.
Dai W, Kerman E, Milenkovic O (2012) A geometric approach to low-rank matrix completion. IEEE Trans Inform Theory 58(1): 237-247.
Dennis JE Jr, Schnabel RB (1983) Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall series in computational mathematics. Prentice Hall Inc., Englewood Cliffs.
do Carmo MP (1992) Riemannian geometry. Mathematics: theory & applications, Birkhäuser Boston Inc., Boston, translated from the second Portuguese edition by Francis Flaherty.
Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2): 303-353.
Griewank A, Reddien GW (1985) The approximation of simple singularities. In: Numerical boundary value ODEs (Vancouver, B. C., 1984), Progr. Sci. Comput., vol 5, Birkhäuser, pp 245-259.
Helmke U, Moore JB (1994) Optimization and dynamical systems. Springer, London.
Helmke U, Shayman MA (1995) Critical points of matrix least squares distance functions. Linear Algebra Appl 215: 1-19.
Keshavan RH, Montanari A, Oh S (2010) Matrix completion from noisy entries. arXiv: 0906. 2027v2.
Meyer G (2011) Geometric optimization algorithms for linear regression on fixed-rank matrices. PhD thesis, University of Liège.
Mishra B, Apuroop KA, Sepulchre R (2012a) A Riemannian geometry for low-rank matrix completion. arXiv: 1211. 1550.
Mishra B, Meyer G, Bach F, Sepulchre R (2011a) Low-rank optimization with trace norm penalty. arXiv: 1112. 2318v1.
Mishra B, Meyer G, Bonnabel S, Sepulchre R (2012b) Fixed-rank matrix factorizations and Riemannian low-rank optimization. arXiv: 1209. 0430v1.
Mishra B, Meyer G, Sepulchre R (2011b) Low-rank optimization for distance matrix completion. In: Decision and control and European control conference (CDC-ECC), 2011 50th IEEE conference on, pp 4455-4460.
O'Neill B (1966) The fundamental equations of a submersion. Mich. Math J 13: 459-469.
O'Neill B (1983) Semi-Riemannian geometry, pure and applied mathematics, vol 103. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York.
Simonsson L, Eldén L (2010) Grassmann algorithms for low rank approximation of matrices with missing values. BIT Numer Math 50(1): 173-191.
Smith ST (1994) Optimization techniques on Riemannian manifolds. In: Bloch A (ed) Hamiltonian and gradient flows, algorithms and control, Fields Inst. Commun., vol 3. Am. Math. Soc. Providence, RI, pp 113-136.
Vandereycken B (2013) Low-rank matrix completion by Riemannian optimization. SIAM J Optim 23(2): 1214-1236.