Spectral norm and maximal inner product of column vectors

Question

Let $A \in \mathbb{R}^{m \times n}$ be a matrix with columns $\{ a_k\}$ such that \begin{align*} \max_{j \neq k} \left| \langle a_j, a_k \rangle\right| \leq \epsilon, \;\;\| a_k \| = 1 \;\forall k \end{align*} Can we bound $\| A\|_2$ in terms of $\epsilon$ and the dimensions of the matrix?

Clearly, if $\epsilon = 0$, we have orthonormal columns and thus $\| A\|_2 = 1$. I can see that if we relax the orthogonality constraint a little bit, the maximum singular value would grow with $\epsilon$, but I was unable to obtain a tight upper bound.

Answer 1

Consider $||Ax||^{2}_{2}$. \begin{equation} ||Ax||^{2}_{2} = \langle Ax \,, Ax \rangle = x^T A^T Ax \end{equation} $A^TA$ is symmetric and positive semi-definite. The eigenvalues of $A^TA$ are real and positive. The eigenvectors of $A^TA$ are orthogonal. Let $\{\beta_i\}_{i=1}^{n}$ denote the orthonormal eigenvectors of $A^TA$.
The corresponding eigenvalues will be denoted by $\lambda =\{\lambda_i\}_{i=1}^{n}$. Any vector $x \in R^n$ can be expanded in the basis $\{\beta_i\}_{i=1}^{n}$. With this,$||Ax||^{2}_{2}$ can be written as \begin{align*} ||Ax||^{2}_{2} = x^T A^T Ax &=\left(\sum_{i} c_{i} \beta_i^{T}\right) A^T A\left(\sum_{j} c_{j} \beta_{j}\right)\\ & =\left(\sum_{i} c_{i} \beta_i^{T}\right) \left(\sum_{j} c_{j} A^T A\beta_{j}\right) =\left(\sum_{i} c_{i} \beta_i^{T}\right) \left(\sum_{j} c_{j} \lambda_j \beta_{j}\right)\\ &= \sum_{i} \sum_{j} c_{i} c_{j}\lambda_{j} \beta_{i}^T \beta_{j} = \sum_{i} \sum_{j} c_{i} c_{j}\lambda_{j} \delta_{i,j} \\ &= \sum_{i} c_{i}^{2}\lambda_{i} \end{align*} To bound $||Ax||^{2}_{2}$, we note that \begin{equation} \min(\lambda) \sum_{i} c_{i}^{2} \le\sum_{i} c_{i}^{2}\lambda_{i} \le \max(\lambda) \sum_{i} c_{i}^{2} \Longrightarrow \min(\lambda) ||x||^{2} \le ||Ax||^{2}_{2} \le \max(\lambda) ||x||_{2}^{2} \end{equation} It remains to find the minimum and maximum eigenvalues of $A^TA$ via Gre$\check{s}$gorin theorem. Let $A^{i}$ denote the $i$ column of $A$. With the assumption that $A$ has unit-norm columns in consideration, Tthe $(i,j)$ the entry of $A^TA$ is given by \begin{equation} (A^TA)_{(i,j)} = \begin{cases} 1 \quad &i=j \\ \langle A^{i}\,,A^{j}\rangle \quad &i\neq j \end{cases} \end{equation} From Gre$\check{s}$gorin theorem, the eigenvalues of $A^TA$ with entries $(A^TA)_{(i,j)}$, $1\le i,j\le n$, lie in the union of disks $d_i = d_i(c_i,r_i)$, $1\le i\le n$, centered at $1$ with radius $$ r_{i} = \sum_{j\neq i} |A^TA|_{(i,j)} = \sum_{j\neq i} |\langle A^{i}\,,A^{j}\rangle| \le (n-1)\epsilon $$ where the last bound follows from the coherence of $A$ i.e $\mu = \max_{1\le i,j \le n} |\langle A^{i}\,,A^{j}\rangle |$. With this, $\min(\lambda)\ge 1-(n-1)\epsilon$ and $\max(\lambda)\le 1+(n-1)\epsilon$. Using these bounds \begin{equation} \left(1-(n-1)\epsilon\right) ||x||^{2} \le ||Ax||^{2}_{2} \le \left(1+(n-1)\epsilon\right) ||x||_{2}^{2} \end{equation}

Answer 2

You have $$\|A\|^2=\|A^*A\|$$ and $A^*A=(\langle a_j,a_k\rangle)_{kj} =I+B$, where $b_{kk}=0$ and $|b_{kj}|<\epsilon $ if $k\ne j $. If we write $B=\sum_{k,j}b_{kj}E_{kj} $, then $$\tag{*}B=\sum_{j=2}^n\,\sum_{k=1}^{n-j}b_{k,j+k}\,E_{k,j+k} + \sum_{k=2}^n\,\sum_{j=1}^{n-j}b_{j,j+k}\,E_{j,j+k}. $$ The point is that \begin{align}\tag{**} \left\| \sum_{k=1}^{n-j}b_{k,j+k}\,E_{k,j+k}\right\|^2 &=\left\| \sum_{k,h=1}^{n-j}b_{k,j+k}\overline {b_{h,j+h}}\,E_{j+h,h}E_{k,j+k}\right\| = \left\| \sum_{k=1}^{n-j}|b_{k,j+k}|^2E_{j+k,j+k}\right\|\\ \ \\ &= \max_k|b_{k,j+k}|^2 \leq \epsilon^2. \end{align} Using the triangle inequality in (*) with the estimate from (**) we get $$\|B\|\leq2 (n-1)\epsilon, $$ and so $\|A\|^2\leq1+\|B\|\leq1+2 (n-1)\epsilon $, giving $$\|A\|\leq \sqrt {1+2 (n-1 )\epsilon}. $$