TransWikia.com

Matlab - Fast Computation of Truncated SVD / PCA

Computational Science Asked on October 23, 2021

I’m working with a Matlab codebase wherein I’m attempting to solve A*c = b by approximating the (square) matrix A with its q largest principal components (basically using the rank-q PCA approximation of A). I’m currently doing that by writing c = pinv(A, tol)*b, where tol is the qth largest singular value of A. This works; however, even if q=1, the method is slow, because I think Matlab’s pinv is computing the full SVD of A under the hood when something simpler like power method should suffice.

Is there a more appropriate/faster Matlab routine for approximating the inverse of A based on its truncated/incremental SVD? For example, is there a way to get just the largest q singular vectors/values of A, without computing any other singular vectors/values? I have been computing the full [U,S,V]=svd(A) and then taking the columns/values I want, but that is not efficient.

I’m aware I could implement the power method and deflation by myself — and may end up doing that — but my specific question is about the most computationally efficient way to complete this task using built-in Matlab routines (and as few as possible). If Matlab has no good built-in ways to do this I’m open to suggestions of third-party Matlab packages as well which would provide this functionality efficiently; e.g. I’ve seen IncPACK2 which seems at a glance to do the right thing (though it’s no longer maintained…).

One Answer

Pseudoinverse can be computed using the SVD $A = USV^top$ by: $$ A^+ = VSigma^+ U^top $$ where $Sigma^+$ is formed from $Sigma$ by taking the reciprocal of all the non-zero elements. With that in mind, you could use MATLAB's svds function as follows:

[U,S,V] = svds(A,k); 
Ainv = V*diag(1./diag(S))*U';

Here k refers to the rank and svds computes only a subset of singular values and vectors. Due to the use of Krylov subspace methods, it also allows to limit other factors such as subspace-dimension.

Answered by Tolga Birdal on October 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP