Main Content

Compute SVD of low-rank matrix sketch

`[`

returns the singular value decomposition (SVD) of a low-rank matrix sketch of input matrix
`U`

,`S`

,`V`

] = svdsketch(`A`

)`A`

. The matrix sketch is a low-rank approximation that only reflects the
most important features of `A`

(up to a tolerance), which enables faster
calculation of a partial SVD of large matrices compared to using
`svds`

.

Use

`svdsketch`

when you do not know ahead of time what rank to specify with`svds`

, but you know what tolerance the approximation of the SVD should satisfy.`svds`

computes the best possible rank-k approximation of the SVD (using the default`"largest"`

method).`svdsketch`

does not guarantee its rank-k approximation is the best one, which accounts for its speed advantage over`svds`

.

`svdsketch`

applies a tolerance to form a low-rank matrix approximation $$A\approx QB$$ of the input matrix `A`

. This low-rank approximation is
called a *matrix sketch*. The matrix sketch only preserves important
features from `A`

, filtering unnecessary information out. The relative
approximation error `apxErr`

of the matrix sketch aims to satisfy the
specified tolerance `tol`

:

$${e}_{\text{sketch}}=\frac{{\Vert QB-A\Vert}_{F}}{{\Vert A\Vert}_{F}}\le tol$$

The process `svdsketch`

follows to form the matrix sketch is:

`svdsketch`

forms the matrix sketch iteratively, with each iteration adding new columns to*Q*and new rows to*B*. The new columns and rows are created by extracting features from`A`

using a random sample matrix. You can control the number of columns and rows added in each iteration with the`BlockSize`

name-value pair.During each iteration,

`svdsketch`

uses power iterations to improve the orthogonality of the new columns in*Q*. You can adjust the number of power iterations with the`NumPowerIterations`

name-value pair.The iterations to form the matrix sketch stop when: the number of columns in

*Q*and rows in*B*reach the specified value for`MaxSubspaceDimension`

, the number of iterations reaches`MaxIterations`

, or the relative approximation error converges (`apxErr <= tol`

).To improve convergence speed,

`svdsketch`

might increase the specified initial value for`BlockSize`

from iteration to iteration if the decay in`apxErr`

is not sufficient.

After the matrix sketch $$A\approx QB$$ is formed, `svdsketch`

computes the singular value
decomposition (SVD) of the matrix sketch via `[U1,S,V] = svd(B,'econ')`

, such
that

$$A\approx QB=\left(Q{U}_{1}\right)S{V}^{H}=US{V}^{H}.$$

If `svdsketch`

is able to filter out some features of
`A`

based on the specified tolerance, then the resulting SVD factors
contain fewer singular values and singular vectors than if a full SVD was performed on
`A`

.

[1] Yu, Wenjian, Yu Gu, and Yaohang
Li. “Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation.”
*SIAM Journal on Matrix Analysis and Applications* 39, no. 3 (August
2018): 1339–1359. https://doi.org/10.1137/17M1141977.