Procrustean Matrix Decomposition and Two-to-Infinity Norm Singular Subspace Perturbation Bounds

A deterministic and probabilistic row-wise singular subspace perturbation framework (introduced by Joshua Cape, Minh Tang, and Carey E. Priebe in 2019) based on the matrix two-to-infinity induced operator norm $\|\mathbf{A}\|_{2\to\infty} = \sup_{\|\mathbf{x}\|_2=1}\|\mathbf{A}\mathbf{x}\|_\infty = \max_{i \in [p_1]}\|\mathbf{A}_{i\cdot}\|_2$ (Equation 2.1, Proposition 2.1) and an exact four-term *Procrustean matrix decomposition* for perturbed singular subspaces $\widehat{\mathbf{X}} = \mathbf{X} + \mathbf{E} \in \mathbb{R}^{p_1 \times p_2}$. Because $\|\cdot\|_{2\to\infty}$ is not submultiplicative, the framework establishes the sharp asymmetric product inequalities $\|\mathbf{A}\mathbf{B}\|_{2\to\infty} \le \|\mathbf{A}\|_{2\to\infty}\|\mathbf{B}\|_2$ and $\|\mathbf{C}\mathbf{A}\|_{2\to\infty} \le \|\mathbf{C}\|_\infty\|\mathbf{A}\|_{2\to\infty}$ (Proposition 6.5) together with the orthogonal Procrustes alignment $\mathbf{W}_U = \arg\min_{\mathbf{W} \in \mathcal{O}_r}\|\widehat{\mathbf{U}} - \mathbf{U}\mathbf{W}\|_F = \widetilde{\mathbf{U}}_1\widetilde{\mathbf{U}}_2^T$ from the SVD $\mathbf{U}^T\widehat{\mathbf{U}} = \widetilde{\mathbf{U}}_1(\cos\boldsymbol{\Theta})\widetilde{\mathbf{U}}_2^T$ satisfying $\frac{1}{2}\|\sin\boldsymbol{\Theta}\|_2^2 \le \|\mathbf{U}^T\widehat{\mathbf{U}} - \mathbf{W}_U\|_2 = 1 - \cos\theta_1 \le \|\sin\boldsymbol{\Theta}\|_2^2$ (Lemma 6.7). Theorem 3.1 decomposes $\widehat{\mathbf{U}} - \mathbf{U}\mathbf{W}_U$ into four structured perturbation terms without requiring distinct signal singular values: $\widehat{\mathbf{U}} - \mathbf{U}\mathbf{W}_U = (\mathbf{I} - \mathbf{U}\mathbf{U}^T)\mathbf{E}\mathbf{V}\mathbf{W}_V\widehat{\boldsymbol{\Sigma}}^{-1} + (\mathbf{I} - \mathbf{U}\mathbf{U}^T)\mathbf{E}(\widehat{\mathbf{V}} - \mathbf{V}\mathbf{W}_V)\widehat{\boldsymbol{\Sigma}}^{-1} - \mathbf{U}(\mathbf{U}^T\widehat{\mathbf{U}} - \mathbf{W}_U) + (\mathbf{I} - \mathbf{U}\mathbf{U}^T)\mathbf{X}(\widehat{\mathbf{V}} - \mathbf{V}\mathbf{W}_V)\widehat{\boldsymbol{\Sigma}}^{-1}$. This yields deterministic and high-probability uniform row-wise subspace bounds $\inf_{\mathbf{W} \in \mathcal{O}_r}\|\widehat{\mathbf{U}} - \mathbf{U}\mathbf{W}\|_{2\to\infty} = O(\|\mathbf{U}\|_{2\to\infty} + r/\sqrt{p})$ improving on the classical Davis–Kahan–Wedin bound by $1/\sqrt{p}$ for incoherent subspaces even when the top $r$ singular values are repeated, with applications to planted clustering ($\mathbf{Z} + \mathbf{E}$), high-dimensional spiked PCA ($p \gg n$), symmetry-projected matrix denoising, and multi-layer network modularity / community recovery (Sections 1.4 and 4, Theorems 1.1, 3.1, and 4.1–4.4).