Question

Hello,

For an $n \times n$ real matrix, the SVD (Singular Value Decomposition) algorithm is $O(n^3)$. I have large matrices (say $10,000 \times 10,000$) that only have elements on few diagonals, i.e. $M=(m_{i,j})\in \mathbb{R}^{n\times n}$ such that $m_{i,j} =0$ if $|i-j|>k$ ($k$ is set and way smaller than $n$). An, in fact these matrices are highly structured (the are Block Toeplitz with Toeplitz Blocks)

1. Is there a name to describe such "multi-diagonal matrices" matrices (I know about tridiagonal matrices, and these could be seen as a generalization)?
2. More importantly, is there a significantly faster SVD algorithm for these matrices?

Answer 1

It depends on how small $k$ is. If $k^2 \ll n,$ the simple method of computing $M^t M$ (sparsely), then the Cholesky decomposition, then the eigenvalues, works very well. Perhaps less work is using

http://soi.stanford.edu/~rmunk/PROPACK/