Two theorems about incoherence

Question

These are two theorems I have heard being referred to in "folklore" but I cant find the proofs for these in any compressed sensing or high-dimensional probability reviews (like, https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf) that I have looked into.

1. That the maximum value of the magnitude of the inner-product between two different columns of a $d \times N$ ``dictionary" (with normalized columns?) is at least $\sqrt{\frac{N-d}{d(N-1)}}$

2. For any 2 randomly picked orthonormal bases in $\mathbb{R}^d$ the ``likely" (Expected? With high probability?) value of the magnitude of the inner-product between 2 vectors, one from each basis, is $O(\sqrt{\frac{\log d}{d}})$

It would be great if someone can type in the proof (if short) or give a reference to look up the proof!

Answer 1

1. Statement 1 is theorem 2.3 in Grassmannian Frames with Applications to Coding and Communication (2003): $${\rm max}_{k\neq l}|\langle f_k,f_l\rangle|\geq \sqrt{\frac{N-d}{d(N-1)}}$$ for any set of $N$ unit vectors $f_k$ in $d\leq N$ dimensions.

2. For a precise formulation of statement 2, with a proof, see page 2 of these lecture notes:
   $${\rm Prob}\,\left(|\cos\theta|<\sqrt{\frac{\log d}{d}}\right)>1-\frac{1}{d},$$ where $\theta$ is the angle between two randomly chosen unit vectors in $d$ dimensions.
   _{notice a typo at the top of the page in those lecture notes, corrected at the bottom, the square root should extend over the entire fraction}