An Improved Incremental Singular Value Decomposition and New Error Bounds
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914524979789824 |
|---|---|
| author | Zhang, Yangwen |
| author_facet | Zhang, Yangwen |
| contents | The incremental singular value decomposition (SVD) updates a
truncated SVD as new columns arrive, replacing a single large SVD
with a sequence of small ones. In floating-point arithmetic, each
update multiplies the running singular basis by a small orthogonal
factor, and the accumulated product loses orthogonality unless the
basis is reorthogonalized periodically. How often this
reorthogonalization is needed has been an open question; we answer
it by restructuring the algorithm so that rank-preserving updates
are accumulated implicitly and applied in batches, reducing the
number of large orthogonal multiplications from $n$, the stream
length, to $r$, the numerical rank. We prove that this
restructuring preserves the exact-arithmetic output of the original
algorithm and establish two forward-error bounds. First, we sharpen
the existing operator-norm truncation bound from $n\,\texttt{tol}$
to $\sqrt{n}\,\texttt{tol}$, and show the new rate is attained on a
constructive example. Second, under a standard probabilistic
rounding-error model, we prove that the loss of orthogonality of
the computed left factor is independent of the stream length $n$
and depends on $m$, the length of each incoming column, only
through a single $\sqrt{m}$ factor. Numerical experiments confirm both bounds and
demonstrate that the proposed algorithm runs $4.5\times$ to
$34\times$ faster than its closest competitors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_05398 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An Improved Incremental Singular Value Decomposition and New Error Bounds Zhang, Yangwen Numerical Analysis The incremental singular value decomposition (SVD) updates a truncated SVD as new columns arrive, replacing a single large SVD with a sequence of small ones. In floating-point arithmetic, each update multiplies the running singular basis by a small orthogonal factor, and the accumulated product loses orthogonality unless the basis is reorthogonalized periodically. How often this reorthogonalization is needed has been an open question; we answer it by restructuring the algorithm so that rank-preserving updates are accumulated implicitly and applied in batches, reducing the number of large orthogonal multiplications from $n$, the stream length, to $r$, the numerical rank. We prove that this restructuring preserves the exact-arithmetic output of the original algorithm and establish two forward-error bounds. First, we sharpen the existing operator-norm truncation bound from $n\,\texttt{tol}$ to $\sqrt{n}\,\texttt{tol}$, and show the new rate is attained on a constructive example. Second, under a standard probabilistic rounding-error model, we prove that the loss of orthogonality of the computed left factor is independent of the stream length $n$ and depends on $m$, the length of each incoming column, only through a single $\sqrt{m}$ factor. Numerical experiments confirm both bounds and demonstrate that the proposed algorithm runs $4.5\times$ to $34\times$ faster than its closest competitors. |
| title | An Improved Incremental Singular Value Decomposition and New Error Bounds |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2204.05398 |