0
$\begingroup$

Let $A=[a_1,\dots,a_n]\in\mathbb R^{m\times n}$ be a matrix with columns $a_1,\dots,a_n$ having unit norm, i.e., $\|a_i\|=1$ for all $i=1,\dots,n$. Let

$$ L := \lambda_{\max} \left( A^T A \right) $$

and

$$\gamma := \max_{i\neq j} \,\, |\langle a_i, a_j\rangle|$$ be the largest correlation of columns of $A$. In other words, $\gamma$ is the largest (in absolute value) off-diagonal entry of $A^TA$ and is known as the mutual coherence of $A$. It is easy to see that $\gamma\leq 1$.

I observe numerically the following fact when $\gamma$ is close to $1$, then $L$ tends to infinity. Is this a basic fact? If not, how can I formalize this idea?


Motivation. This fact happens in the ISTA algorithm, a solving method for Lasso problem. In this algorithm, if the matrix $A$ has large coherence $\gamma$, then the convergence of ISTA method is very slow since its step size $1/L$ is very small. So I think that we should have a relation between $\gamma$ and $L$.

$\endgroup$
7
  • 1
    $\begingroup$ $\big \Vert A\big \Vert_F^2 = n\implies L\leq n$ with equality iff $A$ is rank one $\endgroup$ Jan 29 at 5:34
  • $\begingroup$ @user8675309 wao. But is there a lower bound for $L$? Since we want to show that $L$ tends to infinity. $\endgroup$ Jan 29 at 9:12
  • $\begingroup$ Isn't $L$ the squared spectral norm of $A$? $\endgroup$ Jan 29 at 11:21
  • 1
    $\begingroup$ The title is misleading. The MC of $A$ but the largest eigenvalue of $A^T A$. Different matrices. $\endgroup$ Jan 29 at 11:23
  • 1
    $\begingroup$ Then why not take the SQRT and use the largest singular value? $\endgroup$ Jan 29 at 11:25

1 Answer 1

1
$\begingroup$

Since $A^TA$ is a symmetric $n\times n$ real matrix, there exists an orthonormal basis $v_1,\dots,v_n$ in $\mathbb{R}^n$ of eigenvectors of $A^TA$. Let $\lambda_k$ denote the eigenvalue corresponding to the eigenvector $v_k$. The eigenvalue Since for each $1\leq k\leq n$ we have $$\|Av_k\|^2=\langle A^TAv_k,v_k\rangle = \lambda_k$$ so that the eigenvalues are nonnegative, and their sum equals the trace of the matrix $A^TA$, $$\sum_{k=1}^n\lambda_k=\sum_{k=1}^n\langle A^TAv_k,v_k\rangle=\hbox{Tr}(A^TA)=\sum_{i=1}^n\langle A^TAe_k,e_k\rangle$$ where $e_k$ is the standard basis. Here the fact that the trace of a matrix can be evaluated via any orthonormal basis was used. It follows that we can bound the sum of the eigenvalues, and therefore also the maximal eigenvalue, by a function of the diagonal elements of the matrix $A^TA$. In particular, it is impossible to cause the maximal eigenvalue to grow indefinitely just by altering the off-diagonal elements. This argument on its own does not yet provide a quantitative connection between the maximal eigenvector and the maximal off-diagonal elements, but it does hint to the fact that the diagonal of the matrix carries much of the information pertinent to the size of the eigenvalues.

$\endgroup$
1
  • $\begingroup$ Thank you so much for your answer! I see the point! just a very small remark $\text{Tr} (A^TA)=n$. $\endgroup$ Jan 29 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.