Spectral norm and maximal inner product of column vectors 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.
 A: 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}
A: 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}. $$
