8

How can I calculate the effective rank of a matrix? I know how to calculate the rank but not how to calculate the effective rank.

Sarina
  • 83
  • 1
    Do you have a definition for what "effective" rank means? – hmakholm left over Monica Apr 27 '14 at 16:23
  • Effective rank meaning "if a singular value is large enough to be a significant rank or not". – Sarina Apr 27 '14 at 16:27
  • x @Sarina: I cannot even parse that. You define a noun, "effective rank" to mean a clause, "if such-and-such". And what does it mean for a "singular value" to be a "significant rank"? – hmakholm left over Monica Apr 27 '14 at 16:31
  • 'A major problem in using SVD as a tool in determining the effective rank of a perturbed matrix is that of distinguishing between significantly small and insignificantly large singular values' - so how can I distinguish between signficantly small and insignificantly large? – Sarina Apr 27 '14 at 17:29
  • More specifically: I have a 8*6 matrix with the singular values 0.608795, 0.356773, 0.271435, 0.091224, 0.015292 and 0.000645. According to matlab (using the standard value for tol), the rank of my matrix is six. Is six also the effective rank of my matrix or could it be that one or more of the singular value(s) would be zero if I could exclude roundoff errors due to finite precision numerical operations and (or) random noises? – Sarina Apr 27 '14 at 17:36

3 Answers3

22

You might be interested in the following publication:

Olivier Roy and Martin Vetterli, The effective rank: A measure of effective dimensionality, 15th European Signal Processing Conference, 2007, available at https://infoscience.epfl.ch/record/110188/files/RoyV07.pdf.

They define "effective rank" as the entropy of the notional distribution obtained by normalising the singular values. The $\ell^1$ norm of the singular values is called the nuclear norm.

It has the property that for an m x n matrix A,

1 <= erank(A) <= rank(A) <= min(m,n)

It has other pleasant properties, and a (reasonably) intuitive geometric interpretation in terms of linear transformations.

episodeyang
  • 103
Lionel Barnett
  • 323
3

I've never heard of the effective rank of a matrix. However, you might probably mean the numerical rank. For a matrix $A$ with singular values $\sigma_1\geq\sigma_2\geq\cdots\geq \sigma_n\geq 0$, the $\epsilon$-numerical rank could be defined as $$ r_{\epsilon}=\min\{r:\;\sigma_r\leq\epsilon\}. $$ So, the relatively small singular values are considered to be zero depending on the given "tolerance" $\epsilon$. Usually (when deciding whether or not a given matrix is numerically rank-deficient or not), $\epsilon\approx u\sigma_1$, where $u$ is the machine precision.

Algebraic Pavel
  • 22,928
  • @ Algebraic Pavel , indeed it is a very good definition. The only problem is the cost calculation; when $\epsilon =0$, the cost is $<n^3$, otherwise we must calculate an approximation of the eigenvalues of $AA^T$. When $B$ a generic matrix, the cost of the calculation of an approximation of $Spectrum(B)$ is at least $20 n^3$; yet, when $B$ is symmetric, I think that the cost is lower. Do you know what is the cost (with the constant) of the calculation of an approximation of the $(\sigma_i)$ ? –  Nov 01 '15 at 11:43
  • @loupblanc For a generic $A$, it requires a full SVD (or singular values; the vectors are not needed). This is of course in a sense equivalent to the orthogonal eigen-decomposition if $A$ is symmetric but I do not have the constants of the $O(n^3)$ cost in my head. In this context, the approximation of a particular singular/eigen value does not make much sense if the rank can be anywhere between $1$ and $n$. – Algebraic Pavel Nov 03 '15 at 23:51
0

I saw the use of effective rank of a matrix in the paper Vishwanathan, S. Vichy N., et al. "Graph kernels." The Journal of Machine Learning Research 11 (2010): 1201-1242.

There it is mentioned that the effective rank of a matrix is the number of distinct eigenvalues.

Eigenvalues of a matrix $A$ can be obtained by solving $det(A-\lambda I) = 0$

vivkul
  • 99
  • 7