\section{Introduction}
\label{sec:intro}
A fundamental task in machine learning and modern data analysis is to infer the latent structure underlying unlabeled datasets that are composed of a mixture of several components \cite{TowardsKmeans}. For example, digital pathology images are represented by high-dimensional vector spaces  corresponding to the number of pixels. However, a few relevant features  are often sufficient to identify groups of similar images \cite{peikari2018cluster}. Therefore, a flexible approach for modeling heterogeneous datasets focuses on the assumption that data points are drawn from a union of unknown subspaces, where the dimension of each subspace describes the number of degrees of freedom. This problem is known as subspace clustering (SC), which consists of partitioning the data into multiple clusters and fitting each cluster with a low-dimensional subspace \cite{VidalSubspace,soltanolkotabi2012geometric,soltanolkotabi2014robust,mcwilliams2014subspace}.

A number of approaches to subspace clustering have been proposed in the literature such as algebraic, statistical, and spectral clustering methods; see \cite{elhamifar2013sparse} for a review. Among existing techniques, SC methods based on the self-expressiveness property \cite{elhamifar2009sparse} are popular due to their great empirical success and theoretical guarantees. This line of work, referred to as sparse subspace clustering (SSC), follows a two-step approach. The first step involves representing each data point as a linear combination of all other data points to build an affinity matrix of a graph with vertices corresponding to data points. The second step of SSC  applies normalized spectral clustering \cite{von2007tutoria}  to the learned affinity matrix.

While SSC has drawn significant attention over the past few years, the computational complexity of these methods has to date stood as an obstacle when analyzing large datasets. The construction of affinity matrices incurs high computational cost as one should search for a regularized representation of every single data point with respect to the whole dataset. Moreover, spectral clustering is computationally expensive on large-scale datasets because it involves an eigenvalue decomposition. A straightforward implementation of spectral clustering has a cubic time complexity with respect to the number of data points. However, there are approximate algorithms which run in quadratic time with respect to the size of data \cite{yan2009fast,tian2014learning,pourkamali2016randomized,chen2018spectral}. As a result, the overall computational complexity (quadratic or cubic) in the input size renders existing SSC algorithms  expensive or even prohibitive in the presence of large-scale data.

This paper presents a new method for reducing the computational burden of SSC when the number of data points is large. Given a dataset, the proposed method first selects a small subset of the input data called landmarks, and then represents each data point as a linear combination of the landmarks (rather than the entire dataset as in SSC). The underlying idea is that the required number of data points for solving the SSC problem is proportional to the number of subspaces and their intrinsic dimensions \cite{soltanolkotabi2014robust}. In this paper, we consider two efficient landmark selection strategies: (1) uniform sampling, where a  subset of the input data is selected uniformly at random; and (2) nonuniform sampling scheme by  obtaining a rough approximation of partitioning the input data using K-medoids clustering \cite{park2009simple}. The latter is more suitable to select representative points from all clusters present in the dataset.

The second contribution  is to show that the spectral embedding of the input data  can be obtained efficiently without the need to explicitly form affinity matrices and compute their eigenvalue decompositions. In fact, the computational cost of spectral clustering in our proposed method scales linearly with the data size when the number of landmarks is fixed. Thus, the use of landmarks in our proposed method allows us to simultaneously reduce the computational cost associated with both steps of SSC. Whereas previous methods primarily attempt to reduce the computational cost of the first step, and rely heavily on forcing affinity matrices to be sparse.

The rest of this paper is organized as follows. Section \ref{sec:prelim} provides the SSC problem formulation and a brief overview of prior art. Section \ref{sec:method} introduces the proposed  SSC method for large-scale data using landmarks. Extensive experiments in Section \ref{sec:illust} demonstrate the effectiveness and computational benefits of our method in comparison with existing algorithms, while Section \ref{sec:conc} provides concluding remarks.

\section{Preliminaries}
\label{sec:prelim}
Consider  a set of $n$ data points $\mathcal{X}=\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}\subseteq \mathbb{R}^D$ that are drawn from a union of $K$ subspaces $\{\mathcal{S}_k\}_{k=1}^K$ as follows
\begin{align}
\mathbf{x}_i=\mathbf{H}_k\mathbf{z}_i+\mathbf{e}_i,\;\forall \mathbf{x}_i\in\mathcal{S}_k, \label{eq:data}
\end{align}
where the columns of $\mathbf{H}_k\in\mathbb{R}^{D\times d_k}$ form an orthonormal basis of $\mathcal{S}_k$. Thus, $d_k<D$ is the dimensionality of $\mathcal{S}_k$, $\mathbf{z}_i\in\mathbb{R}^{d_k}$ is the low-dimensional representation of $\mathbf{x}_i$ with respect to $\mathcal{S}_k$, and  $\mathbf{e}_i\in\mathbb{R}^D$ is the noise vector. Given the unlabeled dataset, subspace clustering (SC) aims to recover the underlying subspaces  and the segmentation of  points according to the subspaces. Once   data-to-subspace assignments are obtained, one can recover the subspaces $\{\mathcal{S}_k\}_{k=1}^K$ using the singular value decomposition on the data associated with each cluster \cite{traganitis2018sketched}.

\subsection{SSC problem formulation}\label{sec:form}
A popular approach to solve the SC problem is to form an affinity matrix based on expressing each data point as a linear combination of other points from its own subspace. That is, we would like to express each data point $\mathbf{x}_j$ in the form of $\mathbf{x}_j=\sum_{i\neq j}c_{ij}\mathbf{x}_i$ such that the coefficient $c_{ij}$ is nonzero when $\mathbf{x}_j$ and $\mathbf{x}_i$ are from the same subspace. Note that if the subspace dimensions $d_k$, $k=1,\ldots,K$, are small compared to $D$, then these coefficients are sparse. Thus, sparse subspace clustering (SSC) solves the following optimization problem
\begin{align}
\min_{\mathbf{c}_j\in\mathbb{R}^n} \|\mathbf{c}_j\|_1+\frac{\lambda}{2} \|\mathbf{x}_j - \sum_{i\neq j}c_{ij}\mathbf{x}_i\|_2^2,\;\forall \mathbf{x}_j\in\mathcal{X},\label{eq:SSC}
\end{align}
where $\|\cdot\|_q$ denotes the $\ell_q$ norm for vectors, $\lambda>0$ is the regularization parameter, and $\mathbf{c}_j=[c_{1j},\ldots,c_{nj}]^T$. Therefore, SSC searches for a coefficient matrix $\mathbf{C}=[\mathbf{c}_1,\ldots,\mathbf{c}_n]\in\mathbb{R}^{n\times n}$ such that $\mathbf{X}\approx \mathbf{X}\mathbf{C}$, where $\mathbf{X}=[\mathbf{x}_1,\ldots,\mathbf{x}_n]\in\mathbb{R}^{D\times n}$ is the data matrix. Using the encoded information about the membership of data points to the subspaces in $\mathbf{C}$, we form a graph with $n$ vertices and the affinity matrix $\mathbf{W}=|\mathbf{C}|+|\mathbf{C}^T|$.

In the second step of SSC, the segmentation of data is found by applying spectral clustering to $\mathbf{W}$. To this end, we form the normalized graph  Laplacian matrix $\mathbf{L}=\mathbf{I} - \mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2}$, where $\mathbf{D}$ is the diagonal degree matrix such that its $i$-th diagonal element is equal to $\sum_{j=1}^{n}w_{ij}$ and $\mathbf{I}$ is the identity matrix. Then, the $K$ eigenvectors $\mathbf{v}_1,\ldots,\mathbf{v}_K\in\mathbb{R}^n$ corresponding to the $K$ smallest eigenvalues of $\mathbf{L}$, or equivalently the $K$ largest eigenvalues of $\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2}$, are found. Finally, K-means clustering \cite{pourkamali2017preconditioned} is performed on the rows of the matrix $\mathbf{V}=[\mathbf{v}_1,\ldots,\mathbf{v}_K]\in\mathbb{R}^{n\times K}$ to obtain  the data-to-subspace assignments for the $n$ input data points.

\subsection{Prior work}\label{sec:prior}
Previous work on developing efficient SSC methods can be divided into two categories. The first line of work aims to reduce the computational cost associated with solving the optimization problem in \eqref{eq:SSC} using the whole dataset. For example, the authors in \cite{elhamifar2013sparse} proposed to use the  alternating direction method of multipliers (ADMM) which takes $O(n^3)$ flops \cite{boyd2011distributed}
\begin{align}
\min_{\mathbf{C}} \|\mathbf{C}\|_1+\frac{\lambda}{2}\|\mathbf{X}-\mathbf{X}\mathbf{C}\|_F^2\;\text{s.t.}\;\text{diag}(\mathbf{C})=\mathbf{0},\label{eq:ADMM}
\end{align}
where $\|\cdot\|_1$ and $\|\cdot\|_F$ represent the matrix $\ell_1$ norm and the Frobenius norm, respectively. Also, $\text{diag}(\mathbf{C})$ is a vector that contains the diagonal elements of $\mathbf{C}$ so that we avoid the trivial solution of \eqref{eq:ADMM}. Recently, a more efficient implementation of ADMM for SSC was  introduced with a cost that is quadratic in $n$ \cite{pourkamali2018efficient}. Furthermore, the authors in \cite{you2016scalable} proposed to use orthogonal matching pursuit (OMP) for finding sparse representations  by enforcing a strict $\ell_0$ sparsity constraint instead of the $\ell_1$ norm. The resulting SSC-OMP algorithm is more efficient than ADMM (roughly quadratic in $n$ depending on the specific implementation). It is worth noting that  the described methods mainly focus on the construction of affinity matrices, and the spectral clustering step  still involves  eigenvalue decompositions of $n\times n$ matrices.

A recent work \cite{you2018scalable} takes a different approach by  selecting a small subset of $\mathcal{X}$ that represents all data points. Each  point in the dataset is then expressed as a linear combination of points in the selected subset $\mathcal{X}_0\subseteq\mathcal{X}$ of size $m<n$
\begin{align}
\min_{\mathbf{c}_j\in\mathbb{R}^m} \|\mathbf{c}_j\|_1+\frac{\lambda}{2}\|\mathbf{x}_j - \sum_{i: \mathbf{x}_i\in\mathcal{X}_0}c_{ij}\mathbf{x}_i\|_2^2,\;\forall \mathbf{x}_j\in\mathcal{X}.\label{eq:EX}
\end{align}
The authors in \cite{you2018scalable} also proposed a new method for selecting the subset $\mathcal{X}_0$ based on minimizing a maximum representation cost of $\mathcal{X}$ (called ESC), and solving the above optimization problem has a linear time complexity in $n$. Geometrically,  a subset of data points is selected to best cover the entire dataset as measured by the Minkowski functional. In this approach, the coefficient matrix $\mathbf{C}=[\mathbf{c}_1,\ldots,\mathbf{c}_n]$ is $m\times n$ and, thus,  spectral clustering cannot be directly applied to $\mathbf{W}$ as explained in Section \ref{sec:form}. To fix this problem, for each $\mathbf{c}_j$, the $t$ nearest neighbors with the largest positive inner products are found, and the corresponding entries of $\mathbf{W}\in\mathbb{R}^{n\times n}$ are set to be $1$.  Spectral clustering is then applied to $\mathbf{A}=\mathbf{W}+\mathbf{W}^T$.

\section{The Proposed Method}
\label{sec:method}
In this section, we introduce an efficient method to reduce the computational complexity of  SSC, while maintaining high levels of clustering accuracy. The key idea behind our  method is that, under the union of subspaces model, the  number of samples required for revealing the underlying structure of the data should be proportional to the number of subspaces $K$ and their intrinsic dimensions $d_1,\ldots,d_K$ (and some other factors such as the noise level). Interestingly, recent research efforts have shown that selecting a small subset of the input data results in accurate and efficient learning of mixture models such as K-means clustering \cite{bachem2018scalable}, Gaussian mixture models \cite{lucic2017training2}, and kernel-based clustering \cite{pourkamali18}. Thus, our goal in this paper is to devise sampling schemes for the SSC problem which will enable complexity-performance tradeoffs.

In this work, we explore two efficient sampling strategies to select a small subset of the original data called landmarks. The first  technique is based on uniform sampling where $m$ points are selected uniformly at random from the set of $n$ input data points $\mathcal{X}$. The main advantage of this method is its negligible computational cost even for very large datasets.

However, a nonuniform sampling mechanism which adapts to the specific structure of $\mathcal{X}$ is useful  when the number of landmarks $m$ is small compared to the data size. To this end, we propose to run the K-medoids clustering algorithm \cite{park2009simple} on the original data $\mathcal{X}$ to  partition the data into $m$ clusters. Then,  $m$ cluster centers or medoids are selected as landmarks $\mathcal{X}_0$ for solving the SSC problem.
We choose K-medoids clustering over K-means for obtaining a rough partitioning of the data because of two main reasons: (1) K-medoids is more robust to noise and outliers; and (2) K-medoids returns an actual point in each cluster.

After selecting $m$ landmarks $\mathcal{X}_0$, we represent each point in $\mathcal{X}$ as a linear combination of landmarks $\mathcal{X}_0$ by solving
\begin{align}
\min_{\mathbf{c}_j\in\mathbb{R}^m} \|\mathbf{c}_j\|_1+\frac{\lambda}{2}\|\mathbf{x}_j - \sum_{i: \mathbf{x}_i\in\mathcal{X}_0\setminus\{\mathbf{x}_j\}}c_{ij}\mathbf{x}_i\|_2^2,\forall \mathbf{x}_j\in\mathcal{X}. \label{eq:our}
\end{align}
A difference between our optimization problem and the one in \eqref{eq:EX} is that our method does not allow any data point to be expressed as a linear combination of itself since such coefficients will degrade the performance of SSC when $m$ is large. The time complexity of solving the above optimization problem is linear in $n$ when the number of landmarks is fixed.

The above optimization problem results in a coefficient matrix $\mathbf{C}$ of size $m\times n$, which encodes information about the similarities between $\mathcal{X}_0$ and $\mathcal{X}$. Obviously, it is not feasible to directly build the affinity matrix $\mathbf{W}$  discussed in Section \ref{sec:form} because $\mathbf{C}$ is not $n\times n$ anymore. To resolve this issue, a naive approach is to explicitly form the $n\times n$ matrix $\mathbf{W}=\widetilde{\mathbf{C}}^T\widetilde{\mathbf{C}}$,  where $\widetilde{\mathbf{C}}=|\mathbf{C}|$ and then construct the normalized Laplacian matrix. We present an alternative approach to efficiently obtain the spectral embedding of the input data. Let us consider the columns of $\widetilde{\mathbf{C}} = [\widetilde{\mathbf{c}}_1,\ldots,\widetilde{\mathbf{c}}_n]\in\mathbb{R}^{m\times n}$, and compute the $i$-th element of the degree matrix $\mathbf{D}$ as follows
\begin{align}
\sum_{j=1}^{n}w_{ij}=\sum_{j=1}^{n} \widetilde{\mathbf{c}}_i^T \widetilde{\mathbf{c}}_j=\widetilde{\mathbf{c}}_i^T\sum_{j=1}^{n}\widetilde{\mathbf{c}}_j.
\end{align}
Hence, one can form a vector $\boldsymbol{\alpha}=\sum_{j=1}^{n}\widetilde{\mathbf{c}}_j\in\mathbb{R}^m$ to compute the $i$-th diagonal element of $\mathbf{D}$ as the inner product between $\widetilde{\mathbf{c}}_i$ and $\boldsymbol{\alpha}$ for $i=1,\ldots,n$. Next, we can find the eigenvalue decomposition of $\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2}$ by computing the singular value decomposition \cite{Martinson_SVD} of $\widetilde{\mathbf{C}}\mathbf{D}^{-1/2}\in\mathbb{R}^{m\times n}$. To see this, let $\mathbf{U}\boldsymbol{\Sigma}\mathbf{P}^T$ be the singular value decomposition of $\widetilde{\mathbf{C}}\mathbf{D}^{-1/2}$, where $\mathbf{U}\in\mathbb{R}^{m\times r}$ and $\mathbf{P}\in\mathbb{R}^{n\times r}$ have orthonormal columns, and $r$ is the rank parameter. Then, we have
\begin{align}
\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2} = (\mathbf{U}\boldsymbol{\Sigma}\mathbf{P}^T)^T(\mathbf{U}\boldsymbol{\Sigma}\mathbf{P}^T)=\mathbf{P}\boldsymbol{\Sigma}^2\mathbf{P}^T.
\end{align}
Therefore, the top  $K$ eigenvectors of $\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2}$ are the same as the top $K$ right singular vectors of $\widetilde{\mathbf{C}}\mathbf{D}^{-1/2}$. As a result, the computational complexity of spectral clustering in our framework is linear with respect to the size of data $n$, which makes it suitable for large-scale datasets. The proposed method for SSC using landmarks is summarized in Alg.~\ref{alg:StandardNys}.

\begin{algorithm}[h]
	\caption{Fast Subspace Clustering (FSC)}
	\label{alg:StandardNys}
	\textbf{Input:}  Data $\mathcal{X}$,  number of landmarks $m$, parameter $\lambda$, number of subspaces $K$

	\textbf{Output:} Segmentation of   $\mathcal{X}$
	\begin{algorithmic}[1]
		\STATE Select $m$ landmarks $\mathcal{X}_0$ using uniform sampling or nonuniform sampling (K-medoids clustering)
		\STATE Solve the optimization problem in \eqref{eq:our} to find $\mathbf{C}\in\mathbb{R}^{m\times n}$
		\STATE $\widetilde{\mathbf{C}}=|\mathbf{C}|$, $\boldsymbol{\alpha}=\sum_{j=1}^n\widetilde{\mathbf{c}}_j$
		\STATE $\mathbf{D}=\text{diag}(\widetilde{\mathbf{C}}^T\boldsymbol{\alpha})$
		\STATE Run the K-means clustering algorithm on the top $K$ right singular vectors of $\widetilde{\mathbf{C}}\mathbf{D}^{-1/2}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{P}^T$
	\end{algorithmic}
\end{algorithm}

\section{Experimental Results}
\label{sec:illust}
In this section, we demonstrate the effectiveness of our method fast subspace clustering for large-scale SSC. To this end,  the performance and time complexity of our method based on uniform sampling (FSC-uniform) and  nonuniform sampling using K-medoids clustering (FSC-nonuniform) are compared with the related work discussed in  Section \ref{sec:prior}. Recall that SSC-ADMM \cite{elhamifar2013sparse}, its modified version \cite{pourkamali2018efficient}, and SSC-OMP \cite{you2016scalable} solve the SSC problem using the full dataset without any landmark selection. To implement these algorithms, we use the code provided by the respective authors for computing the segmentation of data, and the parameters are selected to achieve the best clustering accuracy.

On the other hand, our proposed method and ESC \cite{you2018scalable} choose a set of representative points of size $m$ to solve the reduced SSC problem. The  optimization problems in \eqref{eq:EX}
and \eqref{eq:our} are solved using the SPAMS (SPArse Modeling Software) package \cite{mairal2014sparse}. To perform K-means and K-medoids clustering,  we use MATLAB's built-in functions with the maximum number of iterations is set to be 100; the City Block (Manhattan) distance is used for K-medoids clustering.

The metric we use in this paper to compare the performance of   SSC methods is the clustering accuracy, which measures the maximum proportion of data points that are correctly labeled over all possible permutations of  the returned labels \cite{you2018scalable}. Hence, the clustering accuracy falls between 0 and 1, and values closer to 1 indicate better performance.

In the first experiment, we consider the statistical model explained in \eqref{eq:data}, i.e., $\mathbf{x}_i=\mathbf{H}_k\mathbf{z}_i+\mathbf{e}_i$. This model allows us to control the ambient dimension $D$, the number of subspaces $K$, their dimensions, and the number of points per each subspace. We set parameters $D=16$, $K=5$, and $d_k=6$ for $k=1,\ldots,5$. The columns of the orthonormal matrices $\mathbf{H}_k\in\mathbb{R}^{D\times d_k}$ are drawn uniformly at random from a set of $D$ orthonormal random vectors in $\mathbb{R}^D$. The noise vectors $\mathbf{e}_i\in\mathbb{R}^D$, $i=1,\ldots,n$, are drawn i.i.d.~according to the Gaussian distribution $\mathcal{N}(0,\sigma^2)$, where $\sigma=0.1$.

To demonstrate the impact of landmarks, we set the number of  points per subspace to be $720$, which means that the total number of input data points is $n=3,\!600$. Fig.~\ref{fig:res}(a) shows the mean and standard deviation of clustering accuracy over $20$  trials for varying number of landmarks $m$ in the range of $100$ to $500$. Moreover, the averaged runtime of SSC methods is reported in Fig.~\ref{fig:res}(b). As expected, both SSC-ADMM and its modified version  perform equally well, while the latter is almost two times faster in this experiment. We also see that SSC-OMP is more efficient than SSC-ADMM and its modified version (an order of magnitude faster than ADMM). However,  SSC-OMP is less accurate compared to ADMM which is consistent with prior observations, e.g., \cite{you2016scalable}. In contrast, our proposed FSC-uniform significantly outperforms SSC-OMP and ESC, while it is faster than the other methods by a large margin. In fact, FSC-uniform reaches $90\%$ accuracy  when the number of landmarks is $200$. Furthermore, the nonuniform sampling scheme based on K-medoids clustering is slightly more accurate than FSC-uniform, showing the importance of landmark selection specifically for small values of $m$. Although our FSC-nonuniform and ESC run in roughly the same amount of time,  our method is more accurate than ESC for varying $m$.

\begin{figure*}[t]

	\begin{minipage}[b]{0.49\linewidth}
		\centering
		\centerline{\includegraphics[width=7.8cm]{acc_varyingN}}

		\centerline{{(a) clustering accuracy, fixed $n=3,\!600$}}
	\end{minipage}
	\begin{minipage}[b]{0.49\linewidth}
		\centering
		\centerline{\includegraphics[width=7.8cm]{time_varyingN}}

		\centerline{{(b) runtime, fixed $n=3,\!600$}}
	\end{minipage}

	\medskip
	\medskip
	\begin{minipage}[b]{0.49\linewidth}
		\centering
		\centerline{\includegraphics[width=7.8cm]{acc_varyingN2}}

		\centerline{{(c) clustering accuracy, fixed $m=300$}}
	\end{minipage}
	\begin{minipage}[b]{0.49\linewidth}
		\centering
		\centerline{\includegraphics[width=7.8cm]{time_varyingN2}}

		\centerline{{(d) runtime, fixed $m=300$}}
	\end{minipage}
	\hfill
	\caption{Comparing the performance and efficiency of our  fast subspace clustering (FSC) with the related work on  synthetic datasets. Note that the legend in (a) refers to all other figures in (b), (c), and (d). }
	\label{fig:res}
\end{figure*}

In the next experiment, we consider the same synthetic dataset with a fixed number of landmarks $m=300$ and varying number of data points from $n=3,\!000$ to $n=15,\!000$. The mean and standard deviation of clustering accuracy over $20$ trials are reported in Fig.~\ref{fig:res}(c), and we report the averaged runtime results in Fig.~\ref{fig:res}(d). As we observed in the previous experiment, SSC-ADMM is slower than its modified version so we dropped this method to make the figures easier to read. We see that both versions of our FSC outperform SSC-OMP and ESC, and they almost reach the accuracy of solving the sparse optimization using the entire dataset via ADMM. In terms of running time, we see that our FSC-uniform is faster than the other methods by a large margin and it scales linearly as the number of data points $n$ increases (the average runtime of FSC-uniform for $n=15,\!000$ is about $0.45$ seconds). Thus, the proposed method is suitable for performing SSC on   large-scale datasets. In addition, the computational cost of FSC-nonuniform increases at a lower rate compared to ESC as the number of data points $n$ increases.

In the last experiment, we evaluate the performance of SSC methods on clustering images of handwritten digits. To this end, we use the MNIST dataset which contains gray-scale images \cite{lecun1998gradient}. According to \cite{you2016scalable}, we compute a set of nonlinear features using a scattering convolutional neural network \cite{bruna2013invariant}. Then, we form a feature vector for each original image  of size $28\times 28$ by concatenating coefficients in each layer of the network.  The dimensionality of the resulting feature vector for each image is $3,\!472$, and the authors in \cite{you2016scalable} proposed to reduce the dimensionality of these feature vectors using principal component analysis (PCA) from $3,\!472$ to $500$. To follow the same path, we also perform PCA on the feature vectors. However, one can instead use randomized dimension reduction methods  that are shown to be useful for achieving high accuracy in the SSC framework \cite{Pourkamali_ICML_2014,heckel2017dimensionality,meng2018general}.

In summary, we consider $2,\!000$ images randomly chosen from 4 clusters of digits  2, 7, 8, and 9. Thus, we have a dataset with the ambient dimension $D=500$ and the total number of points $n=8,\!000$, which consists of $K=4$ clusters. Since this dataset has been shown to be well-suited for SSC-OMP \cite{you2016scalable}, we present the averaged clustering accuracy of landmark-based SSC methods for varying values of $m$ in Fig.~\ref{fig:res2} . As we see, our proposed methods outperform ESC by a large margin for all values of landmarks. For small values of $m$, our nonuniform sampling scheme is slightly more accurate than uniform sampling, which again indicates the importance of landmark selection when $m$ is small compared to $n$. However, as the number of landmarks increases, the difference between uniform and nonuniform sampling becomes less significant.

\begin{figure}[h]

	\begin{minipage}[b]{0.98\linewidth}
		\centering
		\centerline{\includegraphics[width=8.5cm]{acc_mnist}}

	\end{minipage}

	\hfill
	\caption{SSC on the MNIST dataset for fixed $n=8,\!000$.}
	\label{fig:res2}
\end{figure}

\section{Conclusion}
\label{sec:conc}
In this paper, we presented an efficient approach to subspace clustering on large-scale datasets using landmarks. Two sampling schemes are used to select a small number of landmarks for solving the sparse optimization problem.  Then, we showed that the resulting coefficient matrix can be directly used for performing spectral clustering to achieve the data segmentation. Thus, our method provides tunable tradeoffs between clustering accuracy and time complexity. Empirically, we observed a significant reduction in computational time, while achieving accurate clustering results competitive with the models trained on the full dataset.

\bibliographystyle{ieeetr}


\chapter{Vis4Vis: Visualization for (Empirical) Visualization Research}

\title*{Vis4Vis: Visualization for (Empirical) Visualization Research}
\institute{Daniel Weiskopf \orcid{0000-0003-1174-1026} \at VISUS, University of Stuttgart, Germany\\ \email{weiskopf@visus.uni-stuttgart.de}\\
ORCID iD: \url{https://orcid.org/0000-0003-1174-1026}\\[2ex]
This is a preprint of a chapter for a planned book that was initiated by participants of the Dagstuhl Seminar 18041 (``Foundations of Data Visualization'') and that is expected to be published by Springer.  The final book chapter will differ from this preprint.}

\renewenvironment{leftbar}[1][\hsize]
{%
    \def\FrameCommand
    {%
        {\color{orange}\vrule width 3pt}%
        \hspace{0pt

    }%
    \MakeFramed{\hsize#1\advance\hsize-\width\FrameRestore}%
}
{\endMakeFramed}

\maketitle

\abstract{Appropriate evaluation is a key component in visualization research. It is typically based on empirical studies that assess visualization components or complete systems. While such studies often include the user of the visualization, empirical research is not necessarily restricted to user studies but may also address the technical performance of a visualization system such as its computational speed or memory consumption. Any such empirical experiment faces the issue that the underlying visualization is becoming increasingly sophisticated, leading to an increasingly difficult evaluation in complex environments. Therefore, many of the established methods of empirical studies can no longer capture the full complexity of the evaluation. One promising solution is the use of data-rich observations that we can acquire during studies to obtain more reliable interpretations of empirical research. For example, we have been witnessing an increasing availability and use of physiological sensor information from eye tracking, electrodermal activity sensors, electroencephalography, etc.  Other examples are various kinds of logs of user activities such as mouse, keyboard, or touch interaction. Such data-rich empirical studies promise to be especially useful for studies in the wild and similar scenarios outside of the controlled laboratory environment. However, with the growing availability of large, complex, time-dependent, heterogeneous, and unstructured observational data, we are facing the new challenge of how we can analyze such data. This challenge can be addressed by establishing the subfield of {\em visualization for visualization (Vis4Vis)}: visualization as a means of analyzing and communicating data from empirical studies to advance visualization research.}

\author{}
\section{Introduction}
\label{sec:introduction}

This position statement primarily focuses on empirical studies with user involvement but also touches other empirical studies that may collect data from technical performance benchmarks to assess the computational characteristics of a visualization system.

I argue that we need to establish a new subfield to address the challenges of empirical evaluation in visualization research:

\leftbar
\mbox{}\\[1ex]
\bf \mbox{}~~~We need {\em visualization for visualization (Vis4Vis)}.\\[0ex]
\mbox{}
\endleftbar

\noindent
The underlying problem is the difficulty in performing an appropriate evaluation for complex visualization systems. For these, many of the traditional approaches to empirical research adopted from other fields cannot be used directly.
Section~\ref{sec:background} provides background references that discuss various aspects of the underlying problems, methodological challenges, and possible solutions.

I argue that one promising route is to use as much information as possible from empirical studies. Unfortunately, many of the traditional methods for user studies and other empirical research in visualization come from other fields and earlier times in which there was much less data accessible from studies. One example of such data that is still underutilized in visualization research is gaze data from eye tracking experiments. Section~\ref{sec:eyetracking} discusses examples of eye tracking in visualization research in more detail. However, there are many other potential sources of sensor data that could be collected. Several of these examples rely on physiological sensors, often in the context of work on human-computer interaction (HCI): electroencephalography (EEG)~\cite{Anderson:2011:USV} and, in general, the use of brain-computer interfaces (BCIs) and EEG for interaction~\cite{Gurkok:2012:BCI}, pervasive BCI~\cite{Peck:2010:YBY}, near-infrared spectroscopy (NIRS)~\cite{Hirshfield:2011:TYB,Strait:2014:RNB},  functional magnetic resonance imaging (fMRI)~\cite{Cui:2011:QCN}, or the combination of
several physiological sensors to characterize emotions~\cite{Wagner:2005:PSE}
or investigate interfaces~\cite{Prendinger:2005:UHP}.

However, data is not restricted to coming from physiological sensors. For example, logging user activities with the visualization interface, based on recording mouse, keyboard, touch, or other ways of interaction, can provide a detailed and rich source of highly relevant information~\cite{Vuillemot:2016:LIV}.
 Other examples are video and audio recordings during user studies that can serve as a basis for think-aloud protocol analysis~\cite{Ericsson:1993:PAV}.

Overall, technological advances for various kinds of sensors and other data sources have made it easy and cost-effective to capture largely increasing amounts of data for empirical visualization research. And with further progress in technology, in particular, for non-stationary or wearable devices for visualization and user studies, we will see even more diverse types of user studies in visualization research. A recent trend in the visualization community addresses immersive analytics~\cite{Marriott:2018:IA}, which will lead to the problem of evaluating visualizations in the context of virtual reality or augmented reality.

With the challenges of empirical research for complex visualizations on the one hand, and opportunities that come with advanced data acquisition on the other hand, we will have to rethink how we can conduct, evaluate, and report empirical studies. With this text, I focus on the issues related to data analysis for the evaluation and reporting of the results of studies based on large, complex, time-dependent, heterogeneous, and unstructured observational data. I argue that visual data analysis and communication is a promising approach to address these issues. Accordingly, I will discuss opportunities and open questions for visualization research.
My proposal for the need for {\em Vis4Vis}, especially in the context of empirical visualization research, extends my position statement that I gave as part of the panel discussion at the 2016 Workshop on Beyond Time And Errors: Novel Evaluation Methods For Visualization (BELIV).\footnote{Panel ``On the Future of Evaluation and BELIV'' with panelists Daniel Weiskopf, Laura McNamara, Mark Whiting, Niklas Elmqvist, and Tamara Munzner, BELIV 2016 (Workshop on Beyond Time And Errors: Novel Evaluation Methods For Visualization) at IEEE VIS 2016. \url{https://beliv-workshop.github.io/2016/schedule.html}}

\section{Background of Empirical Studies}
\label{sec:background}

The relevance of empirical studies for evaluation, especially user-oriented evaluation, is well accepted by the visualization research community.
In general, there are many well-established approaches to empirical studies for visualization and visual analytics~\cite{Carpendale:08:EIV,Plaisant:2004:CIV,Wijk:2013:ECV}. Tory~\cite{Tory:14:USV} provides a recent overview and categorization of user study approaches, covering various quantitative and qualitative methods. Freitas et al.~\cite{Freitas:14:HIC} discuss a user-centered perspective on evaluation.
There are also examples in which different types of study methods are combined, including the combination of usability metrics and eye tracking \cite{Coltekin:2009:EEI}.

Evaluation methodology is the special focus of the series of BELIV Workshops, which investigate approaches beyond the traditional user performance measures of completion time and accuracy. Therefore, many BELIV Workshop papers address topics relevant to this text. For example, Elmqvist and Yi~\cite{Elmqvist:12:PVE} describe a collection of patterns for evaluation, Ellis and Dix~\cite{Ellis:06:EAU} provide an explorative analysis of user studies, Lam and Munzner~\cite{Lam:08:IUQ} discuss quantitative empirical studies in the context of meta analysis, and Anderson~\cite{Anderson:12:EVU} employs cognitive measures for evaluation.

However, the above papers do not focus on empirical studies that use rich sets of observations. However, Kurzhals et al.~\cite{Kurzhals:2014:EVA,Kurzhals:2016:ETE} consider this approach as critical for future and improved evaluation methods for visual analytics. They especially focus on the combination of eye tracking information with traditional task performance indicators, but they also discuss the issue of data fusion integrating further time-oriented data acquired during an empirical study. One example is the combination of eye tracking and interaction logs \cite{Blascheck:2014:TAE}. Kurzhals et al.~\cite{Kurzhals:2014:EVA} call for exploratory data analysis and hypothesis building to address the difficult analysis questions that come with  complex data. In follow-up work, Kurzhals et al.~\cite{Kurzhals:2016:TBV} adopt the perspective of analysis tasks on eye tracking data, with a respective overview of such tasks.

A further step in the direction of integrating different data sources from empirical research into an interactive visual analysis approach was taken by Blascheck et al.~\cite{Blascheck2016:VA2,Blascheck:2016:TUB}: they describe how visual analytics methods can be used to evaluate visual analytics systems, for example, by including think-aloud protocol analysis, eye tracking information, or interaction data from the same experiment. Blascheck et al.~\cite{Blascheck:2016:VAC} enrich this approach by integrating visual data analysis and coding of user behavior.

I argue to follow-up and extend this direction of advanced visualization methods for analyzing complex and rich data sources. This will become particularly relevant for studies that address more complex research questions than in traditional, quite focused, and restricted laboratory studies. A trend in HCI and other communities tries to address realistic scenarios by adopting research in the wild \cite{Crabtree:2013:ISI}, following early work on cognition in the wild from the perspective of anthropology \cite{Hutchins:1995:CW,Lave:1988:CP,Suchman:1987:PSA}. A related evaluation need has been identified in the visualization community by Lam et al.~\cite{Lam:2012:ESI} and Isenberg et al.~\cite{Isenberg:2013:SRP}. They discuss scenarios that go beyond traditional user experience, user performance, or (technical) algorithm performance, for example, how we can evaluate communication through visualization,  visual data analysis and reasoning, or collaborative visual data analysis. I am convinced that the visualization of data-rich recordings will be especially useful for empirical research in such areas.

\section{Example: Eye Tracking Studies and Evaluation}
\label{sec:eyetracking}

Let us use eye tracking studies as one example of experimental research with data-rich observations. Gaze is a highly relevant source of data for empirical visualization research because it provides quite accurate and fast information that can be useful to understand attention, reading patterns, and the like. Even though there is not always a direct interpretation of eye tracking data \cite{Kim:2012:DET}, most studies can be set up in a way that eye tracking provides informative feedback if it is used with the right study design and interpretation of results \cite{Goldberg:10:CIG}. Eye tracking might even be an alternative way to measure indicators of insight \cite{North:2006:TMV}.
Background on eye tracking is described in the books by Duchowski~\cite{Duchowski:2007:ETM} and Holmqvist et al.~\cite{Holmqvist:2011:ETC}.

This section focuses on eye tracking for user studies and how we can visually analyze gaze information acquired in such studies. There are other, yet related applications of eye tracking: For example, gaze can serve as a basis for interaction techniques \cite{Jacob:2003:ETH}, eye movements can be employed for activity recognition \cite{Bulling:2011:EMA,Fathi:2012:LRD},
eye tracking can help identify tasks and abilities of users of information visualizations \cite{Steichen:2013:UAI}, and it can be used to  improve interactive visualization by recommendations built on inferred user interest \cite{Shao:2017:VEL,Silva:2018:LEG} and by adaptive interfaces based on the recognition of user tasks and intent \cite{Silva:2019:ETS}.

Now, let us focus on eye tracking in empirical visualization research. Extending the fundamental visualization pipeline~\cite{Chi:2000:TVT,Haber:1990:VIC}, the process of acquisition and visual analysis of eye tracking data can be described by the pipeline of Figure~\ref{fig:pipeline_eyetracking}, as defined by Kurzhals et al.~\cite{Kurzhals:2016:TBV}. The study data consists of gaze information and---potentially---further complementary data. These are processed and annotated before the mapping to the visualization is computed. The overarching process consists of two interlinked loops:
a foraging loop to investigate and explore the study observables,  and a sensemaking loop for the interpretation of the data~\cite{Pirolli:2005:SPV}. This interpretation may lead to confirming, rejecting, or building new hypotheses.

\begin{figure}[t]
    \centering
        \includegraphics[width=0.95\textwidth]{pipeline_eyetracking.pdf}

    \caption{\label{fig:pipeline_eyetracking}

    Schematic pipeline for the visual analysis of eye tracking data. All stages (data acquisition, processing, mapping, interpretation, gaining insight) are  influenced by the analysis task.
    Figure reprinted by permission from Springer: book chapter by Kurzhals et al.~\cite{Kurzhals:2016:TBV} \copyright{} 2017.}
\end{figure}

Figure~\ref{fig:pipeline_eyetracking} shows that data-rich information from eye tracking leads to a quite complex data analysis problem. General, rather high-level analysis tasks include compare, relate, and detect \cite{Kurzhals:2016:TBV}. There are a number of specific questions such as: on which parameters or data are these tasks performed (independent or dependent variables), do we want to define derived variables from raw data (other types of independent or dependent variables), which visualization techniques support these tasks and data types, what are the eventual research questions that should be answered by the analysis?

There is a comprehensive overview of visualization techniques for eye tracking data \cite{Blascheck:14:SAV,Blascheck:2017:VET}, along with a taxonomy that incorporates types of data, stimuli, and visualization techniques. Alternatively, Andrienko et al.~\cite{Andrienko:2012:VAM} provide a critical assessment and review of geo-inspired visual analytics techniques from the perspective of eye tracking analysis. These overview and review papers are a good starting point for choosing appropriate visualization techniques, depending on the visual analysis problem; see center part of Figure~\ref{fig:pipeline_eyetracking}.

Overall, there has been quite some progress recently in novel and improved visualization techniques to support the evaluation of eye tracking studies. In particular, there are techniques that allow researchers to combine spatiotemporal gaze analysis~\cite{Kurzhals:2013:STV} with the integrated interpretation of scanpaths and areas of interest (AOIs)~\cite{Kurzhals:2014:ISC} (see Figure~\ref{fig:iseecube} for an example), visually compare scanpaths~\cite{Koch:2018:IBS}, examine large sets of gaze trajectories by bundling~\cite{Hurter:2013:BVD}, analyze time-dependent AOIs for long-timespan studies \cite{Muthumanickam:2019:ITV}, work with fixation metrics for the large-scale analysis of information visualizations \cite{Bylinskii:2015:EFM}, show gaze and stimulus simultaneously in a volume representation~\cite{Bruder:2019:STV}, or
relate gaze to data of interest in a visualization~\cite{Jianu:2018:DMT}.

There are many examples of the usefulness of such visual data analysis for eye tracking experiments. Typically, visual data analysis is a critical component in pilot studies that can then inform the design of the study process and statistical evaluation. I just want to briefly sketch a few typical examples of how visualization supported our own previous work on eye tracking evaluation of visualization techniques. One example is an eye tracking study that compares parallel coordinates and scatterplots \cite{Netzel:2017:CET}. Here, the visualization of scanpaths, attention, and AOIs for pilot studies helped us formulate hypotheses that eventually led to an advanced computational description of transitions between AOIs that could be used for statistical testing of complex reading behavior. Similarly, for an eye tracking study on transportation maps~\cite{Netzel:2017:UPR}, visualization allowed us to define a new numerical indicator for geodesic distance plots that served as a basis for statistical inference on reading behaviors. Finally, Burch et al.~\cite{Burch:2013:VTS} showcased many different types of visualization techniques and discussed how they could be used to identify qualitative findings in eye tracking data from a study on tree visualization techniques~\cite{Burch:2011:ETO}: visualization allowed us to identify reading strategies, reasons for the bad performance of radial tree layouts, and spatiotemporal characteristics of the eye tracking information.

\begin{figure}[t]
    \centering
        \includegraphics[width=0.95\textwidth]{iseecube.png}

    \caption{\label{fig:iseecube} Screenshot of the {\em ISeeCube} system~\cite{Kurzhals:2014:ISC}, which combines visual spatiotemporal gaze analysis with AOI-oriented analysis. The spatiotemporal analysis is based on a space-time cube visualization (A) that includes selected scanpaths (B) and the results of clustering controlled by user-specified parameters (C).  The AOI-oriented analysis is supported by hierarchical clustering and scarfplots of AOI sequences (D) and a detailed view of a selected AOI (F). The timeline of the video stimulus allows for temporal navigation (F).
    The screenshot was taken when using {\em ISeeCube}~\cite{Kurzhals:2014:ISC} implemented by Kurzhals. Image \copyright{} 2019 Daniel Weiskopf}
\end{figure}

Despite the advances in visual analysis and the above success stories, Kurzhals et al.~\cite{Kurzhals:2016:ETE} pointed out a number of open issues related to evaluating visualization and visual analytics with eye tracking: we are still missing sufficient methods for scanpath comparison, fusion of different data sources (e.g., gaze with interaction logs or EEG), and practical tools and working analysis systems. Furthermore, Kurzhals et al.\ see the need of linking to cognitive models and translational evaluation of human cognition, which asks for building an interdisciplinary community that combines expertise in computer, cognitive, and social sciences. I think that these issues still remain as challenges today. In particular, the combination of data from different sources is a key aspect that needs to be addressed further. There is a need to reach out beyond eye tracking alone and include various other types of data that we can access during studies.

Another challenge is scalability, especially if we want to address long-timespan studies and/or studies with large numbers of participants, leading to a big data visual analytics problem for eye tracking \cite{Blascheck:15:CPB}. This problem will also arise when visualization is evaluated with pervasive eye tracking \cite{Chuang:2019:UGS}, unconstrained mobile eye tracking, or in-the-wild research, typically with mobile eye tracking glasses. The analysis becomes challenging here because each study participant will see individual stimuli, which makes it hard to register or align gaze data between participants and relate them to the semantics of objects from the stimuli. In fact, the data analysis has to include much analysis for time-varying image data acquired by the world camera of the eye tracking glasses. There are some first attempts in this direction \cite{Kurzhals:2017:VAM} that combine computer-based image analysis with visual interaction, but we are still far from a simple, reliable, and time-efficient analysis process.

Up to now, the discussion has focused on eye tracking as an element of methods for quantitative research. However, for a more comprehensive evaluation approach, qualitative methods should also be considered---typically leading to a combination in the form of mixed methods \cite{Johnson:2007:TDM}. I see an integration of data-rich research methods (often the quantitative ones, especially when based on physiological sensors like eye tracking) with data-poor research methods (often the qualitative ones) as another area where visualization can play an important role.  An example of this research direction is the triangulation of different approaches (here, gaze combined with think-aloud protocol analysis and interaction logs) by Blascheck et al.~\cite{Blascheck2016:VA2,Blascheck:2016:TUB}. Taking this approach further, visual analysis and coding of participants' behavior and actions are possible~\cite{Blascheck:2016:VAC}, integrating data-rich gaze information in the form of word-sized graphics~\cite{Beck:2015:EWS} with other sources of information from experiments.

\section{Generalized Problem Characterization}
\label{sec:generalized}

The above discussion was centered around the specific example of eye tracking studies and the evaluation of the results of such studies. Many of the basic challenges already occur in this context of eye tracking and carry over to other types of studies. This section extends the discussion to a generalized view on visual data analysis for empirical visualization research.

\subsection{Data and Visualization Types}

The choice of visualization technique largely depends on the type of data that needs to be analyzed. In general, observational data will be large, complex, time-dependent, heterogeneous, and unstructured, coming from different types of sensors or information sources. However, in general, we can assume that observational data can be assigned some time stamp, i.e., data even from different sources can be eventually registered along the timeline (even though it might be difficult technically). In other words, the underlying data model is that of a time-dependent data set with different types of time-varying data attributes.

The actual data attributes can be of largely varying type, and they may not be sampled at the same timepoints or same frequency. Some might not even be sampled at points in time, but spread across the timeline or even be associated with the full trial (i.e., the full timeline). There is a large set of potential variables that could be acquired as raw data during the experiments-
Typical types of time-series data consist of multidimensional data, i.e., multiple real-valued fields, or multiple categorical (nominal) data attributes (e.g., categories of events from user logs). Other types of much larger data sources include videos (images) and audio that may, for example, be recorded for protocol analysis or mobile eye tracking. Data may also include information about technical or algorithmic measures of performance \cite{Bruder:2019:ERP,Larsen:2016:PMI,Rizzi:2014:PMV}.
For any kind of such data, we may also obtain measures of reliability or uncertainty, which is relevant for many types of sensor data.

The characterization of data does not stop at the stage of the original or raw data. In fact, many examples of visual analysis work on derived data that might be more informative than raw data. For the example of eye tracking in Figure~\ref{fig:pipeline_eyetracking}, the `analysis data' is typically derived data. Preferably, the derived data is fully automatically computed from the original sources, but there might be cases where user intervention might be required, for example, for the visual-interactive annotation of data.

The choice of visualization technique(s) depends on the type of data to be analyzed. A general strategy is to use multiple coordinated views to support several data attributes~\cite{Roberts:2007:CMV}. More integrated visual representations may lead to better results but typically require a specific visual design. To address the complexity of the data analysis problem and facilitate scalability to large data, interactive visualization is routinely combined with automatic data analysis---such as statistical methods, unsupervised, or supervised learning---in a visual analytics setup. Finally, the choice of visualization may also depend on the independent variables, for example, whether we have to analyze data for individual participants or groups of participates, or whether we need comparative visualization to show differences with respect to independent variables.

\subsection{Analysis and Dissemination Goals}

Of course, the choice of visualization technique also depends on the goals of the analysis. Typical analysis tasks include outlier detection, summarization, aggregation, or grouping. A related perspective on data analysis goals for knowledge discovery in databases (KDD) is provided by Fayyad et al.~\cite{Fayyad:1996:KDD}.  Where possible, automatic data analysis or statistical techniques are employed to support the task, but as discussed above, the typical approach will follow the combination with interactive visualization. In particular, the visual analysis should also include the original input data or stimuli. The analysis of qualitative aspects of studies is especially challenging~\cite{Corbin:2015:BQR}; a general approach is based on coding such qualitative study data \cite{Saldana:2015:CMQ}.

A fundamental issue of any visual data analysis is the question of reliability: interactive data exploration might lead to different findings, depending on the interaction steps taken by the analyst. This issue is present for the analysis of study data as well; after all, we want reliable and robust results from studies. Therefore, interactive visualization is typically accompanied by statistical analysis to obtain more controlled answers, yet based on hypotheses informed by visualization.
The sensemaking loop of Figure~\ref{fig:pipeline_eyetracking} indicates hypothesis building and testing for the example of eye tracking experiments; however, the general structure of the sensemaking loop extends to any kind of experimental evaluation and could include statistical testing.

Another issue is related to properly planning the setup of the studies. Their quality critically depends on an appropriate choice of stimuli or other input shown to the participants. Therefore, the generation of input data is of high relevance to support informative results of studies or facilitate benchmarking. A promising approach employs generative data models to do so \cite{Schulz:2016:GDM}.

Finally, the goal of visualization does not stop at data analysis. In fact, visualization is equally relevant for disseminating results of studies after interpretation and insight generation in the sensemaking loop of Figure~\ref{fig:pipeline_eyetracking}. Therefore, visualization approaches for dissemination \cite{Beck:2016:VAD} and storytelling \cite{Lee:2015:MTT,Ma:2012:SSU} are required.

\section{Future Research Perspectives and Call for Action}
\label{sec:action}

Based on the specific observations and experiences with eye-tracking-based empirical visualization research (Section~\ref{sec:eyetracking}) and the generalized problem characterization (Section~\ref{sec:generalized}), I have identified the following, quite subjective recommendations for future research directions and a call for action.

\leftbar
\mbox{}\\[1ex]
\bf \mbox{}~~~Let us be our own domain experts: visualization for visualization ({\em Vis4Vis})!\\[0ex]
\mbox{}
\endleftbar

\noindent
I argue that we should prominently position visualization research as an application domain for visualization. So far, the call for papers and keywords in the paper submission systems of the main conferences of the visualization community (IEEE VIS, EuroVis, PacificVis) specifically ask for application or design study papers, but they do not explicitly consider visualization research---even in cases where they list many other research areas. Furthermore, the call for papers and submission keywords typically contain empirical research, especially user studies, but they focus on actual studies and not on methods that support the evaluation of studies. The series of BELIV Workshops is a good example of a venue that specifically asks for the development of research methods and, thus, implicitly supports the topic of {\em Vis4Vis}. Similarly, the series of Workshops on Eye Tracking and Visualization (ETVIS)\footnote{ETVIS: Workshop on Eye Tracking and Visualization. \url{https://www.etvis.org}} \cite{Burch:2016:ETV} facilitates such research, yet restricted to eye tracking.

To advance our field, a more prominent integration of {\em Vis4Vis} in the main conferences would be helpful.
Being our own domain experts has several benefits. First, we have an intrinsic and tight link to assessing whether our visual data analysis methods work well or how they need to be improved, leading to short development cycles; therefore, we can expect a fast development of useful visualization techniques that may even carry over to applications beyond those for empirical visualization research. Second, we will benefit from improved ways of evaluating our empirical studies, leading to a better understanding of visualization. Finally, since other disciplines such as HCI are facing similar evaluation challenges, there is a potential impact of improved data analysis for empirical research outside the visualization community.

\leftbar
\mbox{}\\[1ex]
\bf \mbox{}~~~Data-driven research for the next generation of empirical studies \\
\mbox{}~~~in visualization!\\[0ex]
\mbox{}
\endleftbar

\noindent
I am convinced that the integration of as-much-as-possible data acquired during studies is a viable way to conduct advanced empirical visualization studies that may support in-the-wild experiments, unconstrained settings, and individual participants and group work alike. Therefore, in the sense of {\em Vis4Vis}, we are facing the challenge of data fusion and combined visual analysis of massive, often messy sensor and other study data. This, in particular, may include various kinds of physiological sensor, image/video, and audio data. However, with the recent progress in machine learning, especially deep neural networks, there is a great potential that we will be able to work with data-rich experiments, with a strong emphasis on data-driven research. In fact, the combination of machine learning with visual analytics is a most promising approach to address these hard analysis problems, for example, in combination with video visual analytics \cite{Hoeferlin:2015:SVV}. In this context, it will be critical to keep the original data as long as possible in the analysis pipeline in order to be able to obtain reliable results. Furthermore, it is equally important to obtain reliable and controlled results for data analysis by complementing visual analysis with rigorous statistical testing.

\leftbar
\mbox{}\\[1ex]
\bf \mbox{}~~~New ways of reporting, privacy preservation, and open science!\\[0ex]
\mbox{}
\endleftbar

\noindent
With extended or new approaches to visual data analysis, we are also facing the issue of how we can report findings from empirical research. One part of this issue is the concise presentation of results, for example, in a research article. Here, traditional styles of reporting by using established statistical descriptions no longer work, but it is not yet clear how the wide variety of more complex analysis results could be summarized in a brief, yet comprehensible and replicable way. Here, visualization can play an important role in the sense of using it for storytelling of the scientific data, but respective methods are yet to be developed.

Another part of this issue is related to how we should communicate the massive data potentially acquired during studies. The straightforward approach is to provide the complete set of research data along with the publication, for example, in repositories that guarantee reliable and long-term access of open research data. However, raw data alone is not useful, and even if meta information is provided, it might still be hard to fully replicate previous studies if they come with complex data. Therefore, it might become relevant to even provide visual analysis tools and descriptions thereof along with the research data. Alternatively, our community could establish a set of tools on which the reproducibility of studies could rely, adopting similar ideas from eye tracking research~\cite{Munz:2019:VMV}. The issues of both storytelling and open science are connected to the development of visual data analysis methods in the sense of {\em Vis4Vis}.

Furthermore, with open empirical data, we have to carefully consider issues related to privacy of participants and research ethics. With data-rich empirical data combined from different types of sensors, we might acquire enough information that could lead to a breach of anonymity if the data is published in original raw format, i.e., there is an intrinsic conflict between open science and privacy preservation. However, visualization has the potential to help here if it is extended toward novel privacy-preserving visualizations integrated into the research process. The outcome could be privacy-preserving, modified versions of the original data that could still be shared as open research data---with sufficient details to support reproducibility of the relevant research results.

\leftbar
\mbox{}\\[1ex]
\bf \mbox{}~~~Best practices for the next generation of evaluation methods!\\[0ex]
\mbox{}
\endleftbar

\noindent
The three areas of recommendations and future research directions mentioned above will have to be complemented by the adoption of the visualization techniques in the processes and reporting of empirical visualization research. To this end, I see an ongoing process of identifying best practices for novel evaluation approaches and establishing new standards of empirical research.

\section{Conclusion}

It is obvious that visualization for visualization ({\em Vis4Vis}) is not the only answer to the challenges that we are facing in improving our set of methods for empirical visualization research.
However, I am convinced that there is room for more advanced visualization methods for data analysis and reporting to be used in the context of studies within the visualization community, eventually improving our approach to empirical research.

\section*{Acknowledgments}

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -- Project-ID 251654672 -- TRR 161 (Project B01 and Task Force TF-B). I thank the participants of the Dagstuhl Seminar 18041 (``Foundations of Data Visualization'') for fruitful discussions. Special thanks to Kuno Kurzhals for the many discussions on eye tracking and visualization. The screenshot in Figure~\ref{fig:iseecube} was taken from his {\em ISeeCube} implementation \cite{Kurzhals:2014:ISC}.