New perturbation bounds for low rank approximation of matrices via contour analysis Article Swipe

MAKE IMPACT

Tran Phuc , Vu, Van · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.08875

Let $A$ be an $m \times n$ matrix with rank $r$ and spectral decomposition $A = \sum _{i=1}^r σ_i u_i v_i^\top, $ where $σ_i$ are its singular values, ordered decreasingly, and $u_i, v_i$ are the corresponding left and right singular vectors. For a parameter $1 \le p \le r$, $A_p := \sum_{i=1}^p σ_i u_i v_i^\top$ is the best rank $p$ approximation of $A$. In practice, one often chooses $p$ to be small, leading to the commonly used phrase "low-rank approximation". Low-rank approximation plays a central role in data science because it can substantially reduce the dimensionality of the original data, the matrix $A$. For a large data matrix $A$, one typically computes a rank-$p$ approximation $A_p$ for a suitably chosen small $p$, stores $A_p$, and uses it as input for further computations. The reduced dimension of $A_p$ enables faster computations and significant data compression. In practice, noise is inevitable. We often have access only to noisy data $\tilde A = A + E$, where $E$ represents the noise. Consequently, the low-rank approximation used as input in many downstream tasks is $\tilde A_p$, the best rank $p$ approximation of $\tilde A$, rather than $A_p$. Therefore, it is natural and important to estimate the error $ \| \tilde A_p - A_p \|$. In this paper, we develop a novel method (based on contour analysis) to bound $\| \tilde A_p - A_p \|$. We introduce new parameters that measure the skewness between the noise matrix $E$ and the singular vectors of $A$, and exploit these to obtain notable improvements, compared to classical approaches in the literature (using Eckart-Young-Mirsky theorem or Davis-Kahan theorem), in many settings. This method is of independent interest and has many further applications.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2511.08875

OA Status

green

OpenAlex ID

https://openalex.org/W7105700937

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7105700937

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2511.08875

Digital Object Identifier

Title

New perturbation bounds for low rank approximation of matrices via contour analysis

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-12

Full publication date if available

Authors

Tran Phuc, Vu, Van

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2511.08875

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2511.08875

Direct OA link when available

Concepts

Low-rank approximation, Mathematics, Singular value decomposition, Dimension (graph theory), Computation, Singular value, Curse of dimensionality, Matrix (chemical analysis), Rank (graph theory), Matrix decomposition, Noise (video), Measure (data warehouse), Algorithm, Approximation error, Intrinsic dimension, Applied mathematics, Approximation algorithm, Moore–Penrose pseudoinverse, Skewness, Effective dimension, Upper and lower bounds, Approximation theory, Synthetic data, Matrix norm, Sparse matrix, Invertible matrix, Perturbation (astronomy), Noisy data, Combinatorics, Linear approximation, Discrete mathematics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload