# Is there a relation between the mutual coherence and largest eigenvalue?

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$$.

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

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.
• Thank you so much for your answer! I see the point! just a very small remark $\text{Tr} (A^TA)=n$. Jan 29 at 9:20