Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
We consider two Riemannian geometries for the manifold <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathcal{M }(p,m\times n)}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">M</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>m</mi> <mo>×</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> of all <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$m\times n$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>m</mi> <mo>×</mo> <mi>n</mi> </mrow> </math> </EquationSource> </InlineEquation> matrices of rank <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>p</mi> </math> </EquationSource> </InlineEquation>. The geometries are induced on <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$${\mathcal{M }(p,m\times n)}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">M</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>m</mi> <mo>×</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> by viewing it as the base manifold of the submersion <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\pi :(M,N)\mapsto MN^\mathrm{T}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="italic">π</mi> <mo>:</mo> <mrow> <mo stretchy="false">(</mo> <mi>M</mi> <mo>,</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> <mo>↦</mo> <mi>M</mi> <msup> <mi>N</mi> <mi mathvariant="normal">T</mi> </msup> </mrow> </math> </EquationSource> </InlineEquation>, selecting an adequate Riemannian metric on the total space, and turning <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$\pi $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">π</mi> </math> </EquationSource> </InlineEquation> 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 on <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$${\mathcal{M }(p,m\times n)}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">M</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>m</mi> <mo>×</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> and to formulate the Riemannian Newton methods on <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$${\mathcal{M }(p,m\times n)}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">M</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>m</mi> <mo>×</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> 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. Copyright Springer-Verlag Berlin Heidelberg 2014
