Monotone convergence of Riemannian gradient descent for the center of mass

Let MM be a Riemannian manifold, let ρrcx\rho\leq r_{\operatorname{cx}}, and let {xi}i=1NB(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 x0B(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 k0k\geq0, with equality only when xk=xˉ2x^k=\bar{x}_2, and xkxˉ2x^k\to\bar{x}_2 as kk\to\infty. More generally, for 2p<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ρ)p2max{p1,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.

Sources & referencesView supporting material

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.