Home / Curated / Algorithms / Scaled Gradient Descent (ScaledGD) for Ill-Conditioned Low-Rank Matrix and Tensor Estimation

Scaled Gradient Descent (ScaledGD) for Ill-Conditioned Low-Rank Matrix and Tensor Estimation

Algorithms AIMech:ScaledGradientDescentForIllConditionedLowRankMatrixEstimation DRAFT

Aliases: ScaledGD, Scaled Gradient Descent for Low-Rank Matrix and Tensor Estimation, Tong-Ma-Chi Preconditioned Factored Gradient Descent

A right-preconditioned nonconvex factored optimization methodology (introduced by Tian Tong, Cong Ma, and Yuejie Chi in 2021) that eliminates the condition-number $\kappa = \sigma_1(\boldsymbol{X}_\star)/\sigma_r(\boldsymbol{X}_\star)$ iteration slowdown of Burer–Monteiro gradient descent across low-rank matrix sensing, matrix completion, robust PCA, and Tucker low-multilinear-rank tensor estimation. Given a loss $f(\boldsymbol{L}\boldsymbol{R}^\top)$ over factors $\boldsymbol{L}\in\mathbb{R}^{n_1\times r}$ and $\boldsymbol{R}\in\mathbb{R}^{n_2\times r}$, ScaledGD updates $\boldsymbol{L}_{t+1} = \boldsymbol{L}_t - \eta\,\nabla_{\boldsymbol{L}} f(\boldsymbol{L}_t\boldsymbol{R}_t^\top)(\boldsymbol{R}_t^\top\boldsymbol{R}_t)^{-1}$ and $\boldsymbol{R}_{t+1} = \boldsymbol{R}_t - \eta\,\nabla_{\boldsymbol{R}} f(\boldsymbol{L}_t\boldsymbol{R}_t^\top)(\boldsymbol{L}_t^\top\boldsymbol{L}_t)^{-1}$ (Equation 3), where the $r\times r$ Gram inverses $(\boldsymbol{R}_t^\top\boldsymbol{R}_t)^{-1}$ and $(\boldsymbol{L}_t^\top\boldsymbol{L}_t)^{-1}$ cost only $O(r^3)$ flops and make the trajectory invariant under arbitrary invertible factor transformations $(\boldsymbol{L}_t\boldsymbol{Q}, \boldsymbol{R}_t\boldsymbol{Q}^{-\top})$ ($\boldsymbol{Q}\in\mathrm{GL}(r)$). By analyzing iterates in the $\boldsymbol{\Sigma}_\star$-scaled distance $\mathrm{dist}^2(\boldsymbol{Z},\boldsymbol{Z}_\star) = \inf_{\boldsymbol{Q}\in\mathrm{GL}(r)}(\|(\boldsymbol{L}\boldsymbol{Q} - \boldsymbol{L}_\star)\boldsymbol{\Sigma}_\star^{1/2}\|_F^2 + \|(\boldsymbol{R}\boldsymbol{Q}^{-\top} - \boldsymbol{R}_\star)\boldsymbol{\Sigma}_\star^{1/2}\|_F^2)$ (Equation 11), where the optimal alignment $\boldsymbol{Q}$ satisfies the cross-symmetry identity $(\boldsymbol{L}\boldsymbol{Q})^\top(\boldsymbol{L}\boldsymbol{Q} - \boldsymbol{L}_\star)\boldsymbol{\Sigma}_\star = \boldsymbol{\Sigma}_\star(\boldsymbol{R}\boldsymbol{Q}^{-\top} - \boldsymbol{R}_\star)^\top(\boldsymbol{R}\boldsymbol{Q}^{-\top})$ (Lemma 10), Theorems 1–4 prove that ScaledGD contracts at rate $\mathrm{dist}(\boldsymbol{Z}_t,\boldsymbol{Z}_\star) \le (1 - 0.6\eta)^t \epsilon_0\sigma_r(\boldsymbol{X}_\star)$ in $O(\log(1/\epsilon))$ iterations completely independent of $\kappa$.

Identity Notes & Concept Scope Resolved against all 442 pinned AIO concepts and 693 maintained AIMech concepts. Distinct from `AIMech:ImplicitRegularizationInNonconvexStatisticalEstimationByLeaveOneOutTrajectoryAnalysis` (Ma, Wang, Chi, & Chen 2020) and `AIMech:ConvexAndNonconvexBridgingForRobustPCAUnderNoiseOutliersAndMissingData` (Chen, Fan, Ma, & Yan 2021), which analyze unpreconditioned factored gradient descent whose iteration complexity scales linearly or quadratically with the matrix condition number $\kappa = \sigma_1(\boldsymbol{X}_\star)/\sigma_r(\boldsymbol{X}_\star)$ and requires explicit balancing regularizers $\|\boldsymbol{L}^\top\boldsymbol{L} - \boldsymbol{R}^\top\boldsymbol{R}\|_F^2$, whereas ScaledGD uses right Gram-inverse preconditioning $(\boldsymbol{R}_t^\top\boldsymbol{R}_t)^{-1}$ to achieve $\mathrm{GL}(r)$ equivariance and $\kappa$-free contraction without balancing penalties.

Claims & Grounded Evidence

3 Claims

Mechanism #claim-glr-reparameterization-equivariance-and-scaled-procrustes-alignment-metric

Under the ScaledGD update $\boldsymbol{L}_{t+1} = \boldsymbol{L}_t - \eta\nabla_{\boldsymbol{L}}f(\boldsymbol{L}_t\boldsymbol{R}_t^\top)(\boldsymbol{R}_t^\top\boldsymbol{R}_t)^{-1}$ and $\boldsymbol{R}_{t+1} = \boldsymbol{R}_t - \eta\nabla_{\boldsymbol{R}}f(\boldsymbol{L}_t\boldsymbol{R}_t^\top)(\boldsymbol{L}_t^\top\boldsymbol{L}_t)^{-1}$ (Equation 3), replacing $(\boldsymbol{L}_t,\boldsymbol{R}_t)$ by $(\boldsymbol{L}_t\boldsymbol{Q},\boldsymbol{R}_t\boldsymbol{Q}^{-\top})$ for any invertible $\boldsymbol{Q}\in\mathrm{GL}(r)$ yields $(\boldsymbol{L}_{t+1}\boldsymbol{Q},\boldsymbol{R}_{t+1}\boldsymbol{Q}^{-\top})$ and leaves the product $\boldsymbol{X}_{t+1} = \boldsymbol{L}_{t+1}\boldsymbol{R}_{t+1}^\top$ exactly invariant (Section 2.1), while Lemma 10 proves that the minimizer $\boldsymbol{Q}$ of the $\boldsymbol{\Sigma}_\star$-weighted distance $\mathrm{dist}^2(\boldsymbol{Z},\boldsymbol{Z}_\star)$ (Equation 11) exists and satisfies the exact alignment equation $(\boldsymbol{L}\boldsymbol{Q})^\top(\boldsymbol{L}\boldsymbol{Q} - \boldsymbol{L}_\star)\boldsymbol{\Sigma}_\star = \boldsymbol{\Sigma}_\star(\boldsymbol{R}\boldsymbol{Q}^{-\top} - \boldsymbol{R}_\star)^\top(\boldsymbol{R}\boldsymbol{Q}^{-\top})$ (Section 2.1, Equation 3; Section 2.3, Equation 11; Appendix A.2, Lemma 10).

supports Source: Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent · Locator: Section 2.1 (Eq. 3, pp. 6-8), Section 2.3 (Eq. 11, pp. 10-12), Appendix A.2 (Lemma 10, pp. 26-28)

Mechanism #claim-condition-number-free-linear-contraction-for-matrix-sensing-and-robust-pca

Theorem 1 and Theorem 3 prove that for rank-$r$ matrix sensing under the Restricted Isometry Property $\delta_{2r} \le c_0$ ($m \gtrsim nr\log n$) and for Robust PCA with sparsity fraction $\alpha \lesssim 1/(\mu^2 r^{3/2}\kappa)$ via entrywise sparsification $\mathcal{S}_\zeta$, spectral initialization followed by ScaledGD with constant step size $\eta \in (0, 2/3]$ satisfies $\|\boldsymbol{L}_t\boldsymbol{R}_t^\top - \boldsymbol{X}_\star\|_F \le 1.5\,\mathrm{dist}(\boldsymbol{Z}_t,\boldsymbol{Z}_\star) \le 1.5(1 - 0.6\eta)^t \epsilon_0\sigma_r(\boldsymbol{X}_\star)$ for all $t\ge 0$, achieving $\epsilon$-accuracy in $O(\log(1/\epsilon))$ iterations independent of $\kappa = \sigma_1(\boldsymbol{X}_\star)/\sigma_r(\boldsymbol{X}_\star)$ (Section 2.2, Theorems 1 and 3; Section 3, Proof of Theorem 1).

supports Source: Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent · Locator: Section 2.2 (Theorem 1, p. 8; Theorem 3, pp. 9-10), Section 3 (pp. 12-16)

Application #claim-projected-scaled-gd-for-matrix-completion-and-tucker-tensor-estimation

Combining ScaledGD with row-wise incoherence projection $\mathcal{P}_B$ on $\|\boldsymbol{L}_{i,\cdot}\boldsymbol{\Sigma}_\star^{-1/2}\|_2$ for matrix completion (Theorem 2, Equations 6–7) and extending to mode-wise Gram-inverse updates $\boldsymbol{U}_k^{(t+1)} = \boldsymbol{U}_k^{(t)} - \eta\nabla_{\boldsymbol{U}_k}f(\mathcal{X}_t)(\breve{\boldsymbol{U}}_k^{(t)\top}\breve{\boldsymbol{U}}_k^{(t)})^{-1}$ and core-tensor update $\mathcal{G}_{t+1} = \mathcal{G}_t - \eta\nabla_{\mathcal{G}}f(\mathcal{X}_t)\times_1(\boldsymbol{U}_1^{(t)\top}\boldsymbol{U}_1^{(t)})^{-1}\cdots\times_3(\boldsymbol{U}_3^{(t)\top}\boldsymbol{U}_3^{(t)})^{-1}$ for Tucker tensor recovery (Section 4, Equation 16, Theorems 4–7) yields condition-number-free linear convergence across matrix completion, tensor sensing, tensor completion, and tensor robust PCA (Section 2.2, Theorem 2; Section 4, Equations 16–20, Theorems 4–7).

supports Source: Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent · Locator: Section 2.2 (Theorem 2, pp. 8-9), Section 4 (Eqs. 16-20, Theorems 4-7, pp. 16-22)

⚠️ Curated Limitations & Negative Results

Requires the target rank r to be specified such that sigma_r(X_star) > 0; if the factorization is over-parameterized with r > rank(X_star), the r x r factor Gram matrices R_t^T R_t and L_t^T L_t become singular or nearly singular as iterates approach X_star, requiring damping (ScaledGD(lambda)).
Guaranteed kappa-free linear contraction requires an initial estimate inside the local basin dist(Z_0, Z_star) <= epsilon_0 sigma_r(X_star), so the sample complexity of spectral initialization still depends polynomially on kappa.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:DimensionalityReduction` Dimensionality Reduction	related_match	Accelerates nonconvex factored low-rank matrix and Tucker tensor estimation via right Gram-inverse preconditioning.
`AIO:PrincipalComponentAnalysis` Principal Component Analysis	related_match	Achieves condition-number-independent linear convergence for ill-conditioned Robust PCA and low-rank matrix completion.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`tmc2021-scaledgd-pdf`	Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent Tian Tong, Cong Ma, Yuejie Chi	primary paper full_text	ID: https://jmlr.org/papers/v22/20-1067.html sha256:213640388a63…
`tmc2021-scaledgd-abs`	Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent (arXiv abstract) Tian Tong, Cong Ma, Yuejie Chi	primary paper abstract_only	ID: https://arxiv.org/abs/2005.08898 sha256:597e3d98316c…
`tmc2021-scaledgd-cr`	Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent (Crossref metadata) Tian Tong, Cong Ma, Yuejie Chi	primary paper abstract_only	ID: https://jmlr.org/papers/v22/20-1067.html sha256:597e3d98316c…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T05:50:00Z

Updated: 2026-10-19T05:50:00Z

Source File: data/curated/ScaledGradientDescentForIllConditionedLowRankMatrixEstimation.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories