\section{Introduction} \label{sec:intro}

\input{1-KFJLT-guarantees-intro-arxiv-v2.tex}

\section{Other Related Work} \label{sec:related-work}

\input{2-KFJLT-guarantees-related-work-arxiv-v2.tex}

\section{Preliminaries} \label{sec:preliminaries}

\input{3-KFJLT-guarantees-prerequisites-arxiv-v2.tex}

\section{Main Results} \label{sec:main-results}

\input{4-KFJLT-guarantees-main-result-arxiv-v2.tex}

\section{Numerical Experiments} \label{eq:experiments}

\input{5-KFJLT-guarantees-experiments-arxiv-v2.tex}

\section{Conclusion} \label{sec:conclusion}

\input{6-KFJLT-guarantees-conclusions-arxiv-v2.tex}

\section*{Acknowledgments}

We would like to thank Tammy Kolda, Ruhui Jin and Rachel Ward for providing feedback on an early version of this work. We also thank the anonymous reviewers for their comments which helped improve the paper.

This material is based upon work supported by the National Science Foundation under Grant No.\ ECCS-1810314.

\bibliographystyle{plainnat}





\subsection{Experiment 1: Synthetic Data}

In this section, we present the results from an experiment which compares five different sketches when applied to random Kronecker vectors with three different random distributions. The five methods we compare are the following.
\begin{itemize}
	\item \textbf{Gaussian} sketch uses an unstructured $J \times \tilde{I}$ matrix with i.i.d.\ standard normal entries which are scaled by $1/\sqrt{J}$. This approach is not scalable, but interesting to use as a baseline in this experiment.
	\item \textbf{KFJLT} is the sketch discussed in this paper, and which is defined in Definition~\ref{def:KFJLT}, with the only difference that the uniform sampling of rows is done without replacement.
	\item \textbf{TRP} is the method proposed in \citep{sun2018}. As sub-matrices, we use matrices with i.i.d.\ standard normal entries of size $I_p \times J$ and rescale appropriately.
	\item \textbf{TensorSketch} is the method developed in \citep{pagh2013, pham2013, avron2014, diao2018}.
	\item \textbf{Sampling} is the method proposed by \citep{cheng2016}. It computes an estimate of the leverage scores for each row of the matrix to be sampled and uses these to compute a distribution which is used for sampling.
\end{itemize}
All of these methods, except the first, are specifically designed for sketching vectors with Kronecker structure. As input, we use random Kronecker vectors $\xbf = \kron_{p=1}^3 \xbf^{(p)}$, where each $\xbf^{(p)} \in \Rb^{16}$ has one of the following distributions.
\begin{itemize}
	\item Each $\xbf^{(p)}$ has i.i.d.\ standard normal entries. 
	\item Each $\xbf^{(p)}$ is sparse with three nonzero elements, which are independent and normally distributed with mean zero and standard deviation 100. The positions of the three nonzero elements are drawn uniformly at random without replacement.
	\item Each $\xbf^{(p)}$ contains a single nonzero entry, which is chosen uniformly at random. This nonzero entry is equal to 100.
\end{itemize}
Sparse Kronecker vectors are interesting in many data science applications, and arise in decomposition of sparse tensors, for example.

In the experiment, we draw two random vectors $\xbf, \ybf \in \Rb^{4096}$, each of which is a Kronecker product of three smaller vectors of length $16$, drawn according to one of the three distributions above. For each of the five sketches $f$ and for some embedding dimension $J$, we then compute how well they preserve the distance between $\xbf$ and $\ybf$ by computing the quantity
\begin{equation} \label{eq:distortion-metric}
	\Big| \frac{\|f(\xbf)-f(\ybf)\|_2}{\|\xbf - \ybf\|_2} - 1 \Big|.
\end{equation}
For each of the three distributions and each embedding dimension
\begin{equation} \label{eq:J-range}
	J \in \{100, 200, \ldots, 1000\}
\end{equation}
we repeat this 1000 times and compute the mean, standard deviation and maximum of \eqref{eq:distortion-metric} over those 1000 trials. 
For $J$ as in \eqref{eq:J-range}, applying one of the sketches to $\xbf$ and $\ybf$ reduces the number of entries in those vectors by between 76\% (for $J=1000$) and 98\% (for $J=100$).
Figures~\ref{fig:experiment1-normal}--\ref{fig:experiment1-large-single} present the results for each of the three distributions.

\begin{figure}[ht!]
	\centering 
	\includegraphics[width=1\textwidth]{experiment1-normal.pdf}
	\caption{Mean, standard deviation, and maximum of the quantity in \eqref{eq:distortion-metric} over 1000 trials when the test vectors are Kronecker products of vectors with i.i.d.\ standard normal entries.}
	\label{fig:experiment1-normal}
\end{figure}

\begin{figure}[ht!]
	\centering 
	\includegraphics[width=1\textwidth]{experiment1-sparse.pdf}
	\caption{Mean, standard deviation, and maximum of the quantity in \eqref{eq:distortion-metric} over 1000 trials when the test vectors are Kronecker products of vectors with three nonzero elements which are independent and normally distributed with mean zero and standard deviation 100.}
	\label{fig:experiment1-sparse}
\end{figure}

\begin{figure}[ht!]
	\centering 
	\includegraphics[width=1\textwidth]{experiment1-large-single.pdf}
	\caption{Mean, standard deviation, and maximum of the quantity in \eqref{eq:distortion-metric} over 1000 trials when the test vectors are Kronecker products of vectors containing a single nonzero entry equal to 100.}
	\label{fig:experiment1-large-single}
\end{figure}

No one method produces the best results for all three distributions. The leverage score sampling approach does very well on dense vectors, even outperforming the Gaussian sketch, but does less well on sparser inputs. Although TensorSketch has an impressive mean performance on the two sparser inputs, it sometimes produces high distortion rates on those inputs. On the sparser inputs, the KFJLT seems to strike the best balance between mean and worst case performance. TRP does poorly for all three distribution types.


\subsection{Experiment 2: MNIST Handwritten Digits}

In this experiment, we consider a subset of the MNIST Handwritten Digits dataset \citep{lecun1998}, which is a standard benchmark dataset in machine learning.\footnote{We downloaded the MNIST dataset using the scripts provided at \url{https://github.com/sunsided/mnist-matlab}.} 
The dataset consists of images of handwritten digits between 0 and 9. 
Each image is in gray scale and of size 28 by 28 pixels. 
To make the image width and height powers of two, we pad the images with zeros so that their size is 32 by 32 pixels.
We arrange 100 images depicting fours into a tensor $\Xe \in \Rb^{32 \times 32 \times 100}$ and 100 images depicting nines into another tensor $\Ye \in \Rb^{32 \times 32 \times 100}$. 
Handwritten fours and nines can look quite similar and can be difficult to distinguish, which is why we choose this particular pair of digits.
We then compute a rank-10 approximate CP decomposition of each tensor using \verb|cp_als| in the Tensor Toolbox for Matlab \citep{bader2006,bader2015}. These take the form
\begin{equation}
\begin{aligned}
	\hat{\Xe} &\defeq \sum_{r=1}^{10} \Abf^{(1)}_{:r} \circ \Abf^{(2)}_{:r} \circ \Abf^{(3)}_{:r} \approx \Xe, \\
	\hat{\Ye} &\defeq \sum_{r=1}^{10} \Bbf^{(1)}_{:r} \circ \Bbf^{(2)}_{:r} \circ \Bbf^{(3)}_{:r} \approx \Ye, \\
\end{aligned}
\end{equation}
where $\circ$ denotes outer product, and each $\Abf^{(1)}, \Bbf^{(1)}, \Abf^{(2)}, \Bbf^{(2)} \in \Rb^{32 \times 10}$ and $\Abf^{(3)}, \Bbf^{(3)} \in \Rb^{100 \times 10}$ are called factor matrices; see \citep{kolda2009} for further details on tensor decomposition.
Notice that the factor matrices require much less storage than the original tensors. Figure~\ref{fig:4-9} shows an example of a four and a nine in the MNIST dataset, and their corresponding approximations in the CP tensors.

\begin{figure}[ht!]
	\centering 
	\includegraphics[width=1\textwidth]{4-9-plot.pdf}
	\caption{Example of a four and a nine with their corresponding approximations.}
	\label{fig:4-9}
\end{figure}

In this experiment, we apply the KFJLT, TRP, TensorSketch and sampling sketches to $\hat{\Xe}$ and $\hat{\Ye}$ to see how well they preserve the distance between these tensors. 
The four sketches can be applied efficiently to $\hat{\Xe}$ and $\hat{\Ye}$ in their decomposed form.
To see this, define $\Xbf \defeq \Abf^{(1)} \odot \Abf^{(2)} \odot \Abf^{(3)} \in \Rb^{102400 \times 10}$ and $\Ybf \defeq \Bbf^{(1)} \odot \Bbf^{(2)} \odot \Bbf^{(3)} \in \Rb^{102400 \times 10}$, and let $\ubf \in \Rb^{20}$ denote a column vector with elements $\ubf_i = 1$ if $1 \leq i \leq 10$ and $\ubf_i = -1$ if $11 \leq i \leq 20$.
Then the following relation holds:
\begin{equation}
	\|\hat{\Xe} - \hat{\Ye}\|_\F = \| [ \Xbf, \, \Ybf ] \, \ubf \|_2,
\end{equation}
where $\|\cdot\|_\F$ denotes the tensor Frobenius norm. 
Since the columns of $[ \Xbf, \, \Ybf ]$ are Kronecker products, each of the four sketches under consideration can be applied efficiently to this matrix. 
The Gaussian sketch requires too much memory and is therefore not considered.  

For any sketch $\Mbf$ with the property 
\begin{equation} \label{eq:M-tensor-sketch}
	\| [ \Xbf, \, \Ybf ] \, \ubf \|_2 \approx \| \Mbf \, [ \Xbf, \, \Ybf ] \, \ubf \|_2,
\end{equation}
we may use $\| \Mbf \, [ \Xbf, \, \Ybf ] \, \ubf \|_2$ as an estimate for $\|\hat{\Xe} - \hat{\Ye}\|_\F$. 
In the case of KFJLT, a guarantee of the form \eqref{eq:M-tensor-sketch} follows from Theorem~\ref{thm:subspace-embedding} when $J$ is large enough.
For each of the four sketches and some embedding dimension $J$, we compute the quantity
\begin{equation} \label{eq:distortion-metric-2}
\Big| \frac{\| \Mbf \, [ \Xbf, \, \Ybf ] \, \ubf \|_2}{\|\hat{\Xe} - \hat{\Ye}\|_\F} - 1 \Big|
\end{equation}
as a measure of performance. 
For each embedding dimension
\begin{equation} \label{eq:J-range-2}
	J \in \{ 100, 200, \cdots, 5000 \}
\end{equation}
we repeat this 1000 times and compute the mean, standard deviation and maximum of \eqref{eq:distortion-metric-2} over those 1000 trials. 
The pair $(\hat{\Xe}, \hat{\Ye})$ remains the same in all trials.
For $J$ as in \eqref{eq:J-range-2}, applying one of the sketches to $[ \Xbf, \, \Ybf ]$ reduces the number of rows by between 95\% (for $J = 5000$) and 99.9\% (for $J = 100$).
Figure~\ref{fig:experiment2} presents the results of the experiment. 
\begin{figure}[ht!]
	\centering 
	\includegraphics[width=1\textwidth]{experiment2.pdf}
	\caption{Mean, standard deviation, and maximum of the quantity in \eqref{eq:distortion-metric-2} over 1000 trials.}
	\label{fig:experiment2}
\end{figure}
All methods have similar performance. 
The fact that the factor matrices are mostly dense (some rows are zero due to the padding) may explain why the occasional large errors for TensorSketch observed in Figure~\ref{fig:experiment1-large-single} are avoided. 
Our results here indicate that the different sketches may have more similar performance on vectors like $[ \Xbf, \, \Ybf ] \, \ubf$ which have less structure than the Kronecker vectors in the synthetic experiment.
\citet{jin2019} made the related observation that KFJLT does a better job of embedding unstructured vectors than Kronecker structured ones; see Section~5.2 in their paper for further details.



