Matlab code to compute the smallest nonzero singular value of the matrix without using SVD

Question

I want to compute the smallest nonzero singular value of the matrix A, which is defined as follows.

Let $B = rand(500, 250)$, $A = B*B^t$, where $t$ denotes the transpose of the matrix.

I found the following matlab code to compute singular values of the matrix A which is based on the Singular value decomposition of the matrix.

svds = svd(A);                             
s = min(svds);  % smallest singular value

I want to know is there any other efficient way to smallest singular value?

Thank you in advance

Answer 1

Since $A=BB^T$, it is symmetric and positive semidefinite, and its singular values are identical to its eigenvalues. Furthermore, its nonzero eigenvalues are identical to the nonzero eigenvalues of $B^TB$. To get the smallest eigenvalue of $B^TB$, use eigs(B'*B,1,'sm').

Answer 2

Summary

The answer is...use svds.

What are the singular values?

There may be some confusion over how you get the singular values. The command svd computes the singular values and the components that you don't want. The command svds only computes the singular values.

As explained here Computing pinv, the first step in computing the full singular value decomposition of a matrix $\mathbf{A}$ is to compute the eigenvalue spectrum of the product matrix $\mathbf{A}^{*}\mathbf{A}$. $$ \sigma = \sqrt{\lambda\left( \mathbf{A}^{*}\mathbf{A} \right)} $$ These are precisely the numbers you want (after they are ordered and $0$ values are culled). These values are returned by svds.

If you want to continue and compute the eigenvectors, and resolve the domain matrices, then execute svd.

Background

For background, the SVD is very powerful, and very expensive. You just want part of the information, and you hope to avoid the performance penalty. But the heart of the complexity of the SVD is the eigenvalue problem. This demands finding the roots of the characteristic polynomial. In your case, a polynomial of order 500. The task of finding roots to general polynomials is a demanding numeric problem. So by asking for the singular values, you have incurred most of the computational cost.

Caution

As an inside, make sure you understand how to handle small singular values. There is a tough issue of deciding if a small eigenvalue is a valid element of the spectrum, or a zero eigenvalue disguised as machine noise. Some discussion is Number of Singular Values and Kernel mapping from feature space to input space.

It may be reasonable to change your requirement from finding the smallest eigenvalue to setting a threshold for smallest eigenvalue.

Keep posting

As your problem and understanding evolve, keep posting and keep the discussion going.

@Rahul's answer

User @Rahul has a better solution because he skips the unneeded step of forming the product matrix. Almost certainly, eigs, svds, and svd call the same routine to find the roots of the characteristic polynomial, and in this instance the time savings may be imperceptible. Failure to recognize that we can bypass the product matrix is a critical oversight.