Gram matrix

For vectors $v_1,\dots ,v_n$, the Gram matrix isTwo finite vector families with the same Gram matrix are related by an isometry between their spans; in finite dimensions that isometry can be extended to a unitary map after completing orthonormal bases.

For a basis $(u_i)$ of a finite-dimensional inner-product space with conjugate-linear first argument, define $G_{ij}=(u_i,u_j)$ and ${\hat{u}}_k={\sum }_l(G^{-1}{)}_{lk}{u}_l$. Then $(u_i,{\hat{u}}_k)={\delta }_{ik}$ and $({\hat{u}}_j,{\hat{u}}_k)=(G^{-1}{)}_{jk}$. This is the inner-product representation of the dual basis; requiring the dual vectors to lie in the given span is essential.

For a matrix $G$ with independent standard normal entries, $G^{T}G/n$ is a Gaussian empirical Gram matrix and has expectation equal to the identity. With mean known to be zero it is the raw empirical second moment. Subtracting a sample mean would give a different estimator. On any fixed unit vector its quadratic form is a chi-squared variable divided by $n$.

For $G$ with $n$ independent standard Gaussian rows in dimension $k$, combine a constant-radius sphere metric net, the quadratic form net bound, the chi-squared concentration inequality, and a union bound. This gives $P(\Vert G^{T}G/n-I_k{\Vert }_{\mathrm{op}}>1/2)\le 2\exp (k\log B-n/1024)$ for a numerical $B$. Taking $n$ larger than a constant times $k\log p$ gives exponential decay in $k\log p$. The subspace is fixed, so no union over supports is needed.

If $E=A^{T}A/d-I$ has entrywise maximum norm at most $t$, every vector $z$ supported on at most $s$ coordinates satisfies $|z^{T}Ez|\le t\Vert z{\Vert }_1^2\le st\Vert z{\Vert }_2^2$. Thus the squared norm distortion is at most $st$ on all such sparse vectors. Use the quadratic inequality at $z=0$, where a ratio would be undefined.