Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument (Q2185843)

Let \(\mathbb{R}^{I}\) be the space of \(I\times J\) real matrices and \(I\)-dimensional real vectors. Let \(\|\cdot\|_2\) be the standard Euclidean norm over \(\mathbb{R}^{I}\). A probability distribution on a family of maps \(\mathcal{F}\), where each \(f\in \mathcal{F}\) maps \(\mathcal{Y}\subseteq \mathbb{R}^I\) to \( \mathbb{R}^J \), is a Johnson-Lindenstrauss transform (JLT) with parameters \(\varepsilon, \delta\), and \(N\) on \(\mathcal{Y}\) if, for any subset \(\mathcal{X}\subseteq \mathcal{Y}\) containing \(N\) elements, the probability of drawing a map \(f\in \mathcal{F}\) which satisfies \[(\forall \, \mathbf{x}, \mathbf{y}\in \mathcal{X})\ \ \ (1-\varepsilon)\|\mathbf{x}-\mathbf{y}\|_{2}^{2} \leq\|f(\mathbf{x})-f(\mathbf{y})\|_{2}^{2} \leq (1+\varepsilon)\|\mathbf{x}-\mathbf{y}\|_{2}^{2}\] is at least \(1-\delta\). A probability distribution on a family \(\mathcal{F}\) of \(J\times I\) matrices is an \((\varepsilon, \delta)\) oblivious \(l_2\)-subspace embedding for \(I\times R\) matrices with columns in \(\mathcal{Y}\subset \mathbb{R}^I\) if, for any matrix \[\mathbf{X}=[\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_R]\ \ \ \mbox{with}\ \ \ \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_R\in \mathcal{Y},\] the probability of drawing a matrix \(\mathbf{M}\in \mathcal{F}\) satisfying \[(\forall \, \mathbf{z}\in \mathbb{R}^R)\ \ \ (1-\varepsilon)\|\mathbf{X}\mathbf{z}\|_{2}^{2} \leq\|\mathbf{M}\mathbf{X}\mathbf{z}\|_{2}^{2} \leq (1+\varepsilon)\|\mathbf{X}\mathbf{z}\|_{2}^{2}\] is at least \(1-\delta\). The authors prove that the Kronecker fast Johnson-Lindenstrauss transform (KFJLT) is an \((\varepsilon,\delta)\) oblivious \(l_2\)-subspace embedding for matrices whose columns have Kronecker structure when the embedding dimension \(J\) is sufficiently large. They provide an alternative proof to show that the KFJLT is a JLT on vectors with Kronecker structure. Compared with the results proposed by \textit{R. Jin}, \textit{T. G. Kolda} and \textit{R. Ward} [``Faster Johnson-Lindenstrauss transforms via Kronecker products'', Preprint, \url{arXiv:1909.04801}], the authors' results have a worse dependence on the ambient dimensions \(I_1, I_2,\dots, I_P\) of the input vectors, but have a better dependence on the accuracy parameter \(\varepsilon.\) Finally, two numerical experiments (synthetic data and MNIST handwritten digits) are presented to compare the KFJLT with four other techniques.