A note on alternating projections for ill-posed semidefinite feasibility problems |
| |
Authors: | Dmitriy Drusvyatskiy Guoyin Li Henry Wolkowicz |
| |
Affiliation: | 1.Department of Mathematics,University of Washington,Seattle,USA;2.Department of Applied Mathematics,University of New South Wales,Sydney,Australia;3.Department of Combinatorics and Optimization,University of Waterloo,Waterloo,Canada |
| |
Abstract: | We observe that Sturm’s error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of (mathcal {O}Big (k^{-frac{1}{2^{d+1}-2}}Big )), where d is the singularity degree of the problem—the minimal number of facial reduction iterations needed to induce Slater’s condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of (mathcal {O}Big (frac{1}{sqrt{k}}Big )). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|