According to Theorem 7.16 of High-Dimensional Statistics: A Non-Asymptotic Viewpoint (M. Wainwright, 2019), we know that for $\mathbf X\in\mathbb R^{n\times p}, X_{ij}\overset{iid}{\sim}N(0,1),$ there are universal positive constants $c_1 < 1 < c_2$ such that $$ \frac{\|\mathbf X\theta\|_2^2}{n}\geq c_1 \|\theta\|_2^2 - c_2 \frac{\log p}{n} \|\theta\|_1^2,\theta\in\mathbb R^p $$ with high probability. I want to derive the lower bound of the following, $$ \frac{\|(\mathbf X \otimes \mathbf X^\top)\theta\|_2^2}{np}, \theta\in\mathbb R^{np} $$ The proof of Theorem 7.16 makes use of the Gordon-Slepian inequality and the variable $\dfrac{\langle u, \mathbf X v\rangle}{\sqrt n}$ is zero-mean Gaussian with variance $n^{-1}$, where $u,v$ are unit vertors. While for $Z_{u,v} = \dfrac{\langle u, (\mathbf X \otimes \mathbf X^\top) v\rangle}{\sqrt n}$, $Z_{u,v}$ is not a Gaussian variable and its mean is not zero, the techniques of Gaussian process cannot be used.
If we consider $\theta = \theta _1 \otimes \theta_2, \theta _1 \in\mathbb R^{p}, \theta _2 \in\mathbb R^{n}$, we can obtain that
$$
\frac{\|(\mathbf X \otimes \mathbf X^\top)\theta\|_2^2}{np}\geq c_1 c_1^\prime \|\theta\|_2^2 - c_2c_1^\prime \frac{\log p}{n} \|\theta_1\|_1^2 \|\theta_2\|_2^2 - c_2^\prime c_1 \frac{\log n}{p} \|\theta_2\|_1^2 \|\theta_1\|_2^2
$$
Since $\|\theta\|_1\geq\|\theta\|_2,$ we can get
$$
\frac{\|(\mathbf X \otimes \mathbf X^\top)\theta\|_2^2}{np}\geq \tilde c_1 \|\theta\|_2^2 - \tilde c_2 (\frac{\log p}{n} + \frac{\log n}{p}) \|\theta\|_1^2
$$
So I guess that the right-hand side of the inequality is the lower bound.
But I don't know how to cope with $\theta$ without the Kronecker structure. Thanks for your help!!!
