Monotone convergence of Riemannian gradient descent for the center of mass

About 15 years old · traced to

Let MM be a Riemannian manifold, let ρ≤rcx⁡\rho\leq r_{\operatorname{cx}}, and let {xi}i=1N⊂B(o,ρ)⊂M\{x_i\}_{i=1}^N\subset B(o,\rho)\subset M. Set xˉ2\bar{x}_2 to be their L2L^2 center of mass, and define HB(o,ρ)=cδ(2ρ)H_{B(o,\rho)}=c_{\delta}(2\rho), where cκc_{\kappa} is the comparison function defined in the paper. Assume x0∈B(o,ρ)x^0\in B(o,\rho) and use the constant step-size tk=tt_k=t with t∈(0,1/HB(o,ρ)]t\in(0,1/H_{B(o,\rho)}]. Monotone convergence conjecture. Every iterate remains in B(o,ρ)B(o,\rho), f2(xk+1)≤f2(xk)f_2(x^{k+1})\leq f_2(x^k) for k≥0k\geq0, with equality only when xk=xˉ2x^k=\bar{x}_2, and xk→xˉ2x^k\to\bar{x}_2 as k→∞k\to\infty. More generally, for 2≤p<∞2\leq p<\infty, the same conclusions hold when t∈(0,1/HB(o,ρ),p]t\in(0,1/H_{B(o,\rho),p}], where HB(o,ρ),p=(2ρ)p−2max⁡{p−1,cδ(2ρ)}H_{B(o,\rho),p}=(2\rho)^{p-2}\max\{p-1,c_{\delta}(2\rho)\}. These conditions give a proposed sharp convergence regime for the algorithm, strengthening the paper's general sufficient convergence results.

References

Primary source

Bijan Afsari, Roberto Tron and René Vidal, “On The Convergence of Gradient Descent for Finding the Riemannian Center of Mass”, arXiv:1201.0925 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.