Yudong Wei

Xinxin Li, Yudong Wei, Hao Zhang

We study the two-set feasibility problem of finding a point in the intersection $X\cap Y$ of closed convex sets in a Hilbert space. We propose a generalized composed alternating relaxed projection algorithm (gCARPA) that blends Douglas-Rachford-type and projection-reflection-type dynamics via an outer averaging step $μ$ and an internal relaxation $(γ,θ,η)$. The algorithm contains several classical projection methods as special cases. We also introduce its non-stationary variant, in which $(γ_k,θ_k,η_k)$ vary over iterations, and establish its convergence. For the subspace feasibility model, we derive an explicit spectral characterization via principal-angle block decompositions, yielding computable subdominant-eigenvalue factors and a minimax parameter-selection recipe in a symmetric regime that targets critical damping on principal-angle planes. Numerical experiments illustrate that the generalized relaxation and its non-stationary tuning can improve or match baseline methods in problem-dependent regimes.

Yudong Wei, Liang Zhang, Bingcong Li et al.

Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank $r$ is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank $r$ larger than necessary and enjoys faster convergence as $r$ increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.