\section{Introduction}

Data-driven linear models are a common approach to modeling multivariate timeseries
and have been studied extensively in the mathematical sciences and applied fields.
These domains include
Earth and atmospheric sciences \citep{leith1978a,danforth2007,alexander2008},
fluid dynamics \citep{rowley2009,allgaier2012,budisic2012,towne2018},
and neuroscience \citep{brunton2016,markowitz2018}.
Even when the underlying dynamics are nonlinear,
such linear approximations may be justified by their
connection to the eigenfunctions of the Koopman operator
\citep{budisic2012,lusch2018},
known as the dynamic mode decomposition
\citep{rowley2009,tu2014,takeishi2017}.
In order to capture non-stationary behavior,
it is important to leverage
dynamic linear models (DLMs)
that vary over time \citep{west1997a}.
However,
since every linear model is parametrized by a
{\em system matrix},
and this matrix changes over time,
a naive DLM fit to a length $T$ timeseries of $N$ variables
has $\mathcal{O}(T N^2)$ parameters, which could be very large.
We propose to manage such complexity by representing the
stack of system matrices as a low rank tensor
with only $\mathcal{O}(T + 2N)$ parameters
(Figure~\ref{fig:schematic}).

There is a rich and extensive literature on DLMs,
including
time-varying autoregressive (TVAR) and
switching linear dynamical systems (SLDS) models
that we cannot review in full here \citep{west1997a}.
Ours is a regularized optimization method
\citep[in the spirit of][]{ghahramani2000,chan2014,chan2015a,yu2016b,tank2017a},
complementary to the Bayesian approaches taken
in much of the literature
\citep{prado2000,fox2009,damien2013,linderman2017}.
We also would like to highlight the recent work of
\cite{costa2019}, which uses likelihood tests to
adaptively segment a timeseries and fit different models
to each segment.
However, our approach is inherently more scalable due to
the low rank assumptions we make.

The key innovation of our model is to parametrize the dynamics
by a low rank tensor for
computational tractability, ease of identification, and
interpretation.
Tensor decompositions \citep{kolda2009} are a powerful technique
for summarizing multivariate data
and an area of ongoing research in theory
\citep[][among others]{ge2017,anari2018}
and applications
\citep[e.g., to improve neural networks][]{novikov2015,he2017}.
In our formulation, the system tensor representing
the DLM is regressed against the data.
In this aspect, our method is most similar to
the work of Yu and colleagues
who considered spatiotemporal forecasting
with spatial smoothness regularization
\citep{bahadori2014,yu2016,yu2018},
in contrast to our temporal smoothness,
although the possibility is mentioned in their dissertation \citep{yu2017a}.
Our work also differs in the emphasis on non-smooth regularization
to find switching or other temporally structured behavior.

\begin{figure*}[]
  \centering
  \includegraphics[width=\textwidth]{tensor_diagram-eps-converted-to.pdf}
  \caption{
    Schematic of the TVART method.
    Time series data are windowed, and a linear model is fit in each window.
    The system matrices across windows are assumed to
    arise from a tensor that is low rank.
    This assumption couples together the different matrices in time
    and factors as a spatiotemporal modal decomposition:
    The left and right spatial
    modes $\U1$ and $\U2$ are a basis
    for the row and column spaces of the system matrices,
    and the temporal modes
    $\U3$ allow their weights to change over time.
    The temporal modes shown in the bottom right correspond to the columns
    of $\U3$.
    We allow the possibility of
    smoothing of the temporal modes in
    order to stabilize the model fit with small window size.
  }
  \label{fig:schematic}
\end{figure*}

\subsection*{Notation}
\label{sec:notation}

We follow the conventions of
\cite{kolda2009} for notation.
In brief, tensors are denoted with calligraphic bold ($\ten{A}$),
matrices with capital bold ($\mat{A}$), and vectors with lower-case bold symbols
($\bf a$).
MATLAB-style colon notation represents slices,
e.g.\ ${\bf A}_{i:}$ is the row vector formed from the
$i$th row of a matrix ${\bf A}$.
All of the tensors we consider are third-order.
For a tensor $\ten{A}$, let
${\bf A}_k = {\ten A}_{::k}$ be its $k$th frontal slice.

\section{The TVART model}

\label{sec:problem_setup}

We now introduce our time-varying autoregressive model with low rank tensors
(TVART, Figure~\ref{fig:schematic}).
Assume we have sampled the trajectory of a
dynamical system
$\bm{x}(t) \in \ensuremath{\mathbb{R}}^N$ for $t = 1, \ldots, \tau+1$.
We split this trajectory into $T$
non-overlapping windows of length $M$,
so that $T M = \tau$.
Let $\ensuremath{\bm{\mathscr{X}}}$ be the $N \times M \times T$ tensor with entries
$
(\ensuremath{\bm{\mathscr{X}}})_{ijk} = x_i ( (k-1)M + j ),
$
and similarly let $\ensuremath{\bm{\mathscr{Y}}}$ be a tensor of the same size with entries shifted
by one time point,
$
(\ensuremath{\bm{\mathscr{Y}}})_{ijk} = x_i ( (k-1)M + j + 1 )
$.
We call the frontal slices
$\ensuremath{\mathbf{X}}_k, \ensuremath{\mathbf{Y}}_k \in \ensuremath{\mathbb{R}}^{N \times R}$
the {\em snapshot matrices} for window $k$.
The first of these are
\[
\ensuremath{\mathbf{X}}_1 = \left[
  \begin{array}{cccc}
    \vert & \vert & & \vert \\
    \bm{x}(1) &\bm{x}(2) &\ldots &\bm{x}(M) \\
    \vert & \vert & & \vert
  \end{array}
\right]
\quad \mbox{and} \quad
\ensuremath{\mathbf{Y}}_1 = \left[
  \begin{array}{cccc}
    \vert & \vert & & \vert \\
    \bm{x}(2) &\bm{x}(3) &\ldots &\bm{x}(M+1) \\
    \vert & \vert & & \vert
  \end{array}
\right] .
\]
The subsequent snapshots $\ensuremath{\mathbf{X}}_k, \ensuremath{\mathbf{Y}}_k$ for $k > 1$
are each shifted by $(k-1)M$.

The goal of TVART is to fit an
$N \times N \times T$
tensor $\ensuremath{\bm{\mathscr{A}}}$ of system matrices, so that
$
\ensuremath{\mathbf{Y}}_k \approx \ensuremath{\mathbf{A}}_k \ensuremath{\mathbf{X}}_k
$
for $k = 1, \ldots, T$,
where $\ensuremath{\mathbf{A}}_k$ is the $k$th frontal slice of $\ensuremath{\bm{\mathscr{A}}}$.
The assumption underlying this goal is that
$
\bm{x}(t+1) \approx \ensuremath{\mathbf{A}}(t) \, \bm{x}(t)
$
where $\ensuremath{\mathbf{A}}(t)$ is constant within a window.
This assumption motivates the least squares optimization problem below,
which is equivalent to assuming uncorrelated Gaussian errors:
\begin{equation}
  \label{eq:TVART}
  \min_{\ensuremath{\bm{\mathscr{A}}}: \; \mathrm{rank} (\ensuremath{\bm{\mathscr{A}}}) = R}

  \,
  \frac{1}{2}\sum_{k=1}^T \| \ensuremath{\mathbf{Y}}_k - \ensuremath{\mathbf{A}}_k \ensuremath{\mathbf{X}}_k \|_F^2 \, .
  \tag{TVART}
\end{equation}
Without the rank constraint, \ref{eq:TVART}
factors into decoupled problems for each window $\ensuremath{\mathbf{A}}_k$.
In order to limit the degrees of freedom in the tensor $\ensuremath{\bm{\mathscr{A}}}$,
we use a low rank formulation.
Specifically, we represent $\ensuremath{\bm{\mathscr{A}}}$ using the
canonical polyadic (CP) decomposition \citep{kolda2009} of rank $R$  as
\[
\ensuremath{\bm{\mathscr{A}}} =
\sum_{r=1}^R
\uvec1_r \circ \uvec2_r \circ \uvec3_r
\]
in terms of the factor matrices
$\U1 \in \ensuremath{\mathbb{R}}^{N \times R}$,
$\U2 \in \ensuremath{\mathbb{R}}^{N \times R}$,
and
$\U3 \in \ensuremath{\mathbb{R}}^{T \times R}$,
where
\begin{equation*}
  \U{i} =
  \left[
    \begin{array}{ccc}
      \vert & & \vert \\
      \uvec{i}_1 & \ldots & \uvec{i}_R \\
      \vert & & \vert
  \end{array}
  \right] .
\end{equation*}
Thus, the number of parameters is reduced to $(2N + T)R$,
which is now linear in $N$ and $T$.
We can optionally normalize the factors to have unit-length columns
and capture their scalings in a vector
$\bm{\lambda} \in \ensuremath{\mathbb{R}}^R$;
we consider this a postprocessing step and explicitly state when we do this.

When solving \ref{eq:TVART} for $\ensuremath{\bm{\mathscr{A}}}$,
we work directly with its frontal slices
\begin{equation}
  \label{eq:slice_modes}
  \ensuremath{\mathbf{A}}_k
  = \U1 \ensuremath{\mathbf{D}^{(k)}} {\U2}^\intercal ,
  \quad \mbox{where} \quad
  \ensuremath{\mathbf{D}^{(k)}} = \mathrm{diag} \left( \uvec3_{k:} \right).
\end{equation}
The matrix $\ensuremath{\mathbf{D}^{(k)}}$ is the $R \times R$ diagonal matrix formed from the $k$th row of $\U3$ \citep{kolda2009}.

\begin{definition}
We call the matrices $\U1$, $\U2$, and $\U3$ the
{\em TVART dynamical modes}.
Specifically, we refer to $\U1$ and $\U2$
as the {\em left and right spatial modes},
since they determine the loadings of $\ensuremath{\mathbf{A}}_k$
onto the spatial dimensions/channels in the data.
The matrix $\U3$ contains the {\em temporal modes},
since it determines the time-variation of the
system matrix $\ensuremath{\mathbf{A}}_k$ across windows.
\end{definition}

In some ways, \eqref{eq:slice_modes} is similar to the
singular value decomposition (SVD):
each slice $\ensuremath{\mathbf{A}}_k$ is the product of a
low rank matrix $\U1$, a diagonal matrix $\ensuremath{\mathbf{D}^{(k)}}$,
and another low rank matrix $\U2^\intercal$.
However, unlike the SVD,
the left and right spatial modes are not orthogonal.
Let
$\U1 = \mat{Q}^{(1)} \mat{R}^{(1)}$ and
$\U2 = \mat{Q}^{(2)} \mat{R}^{(2)}$
be the QR decompositions of the left and right spatial modes,
so that
$\ensuremath{\mathbf{A}}_k = \mat{Q}^{(1)} \mat{R}^{(1)} \ensuremath{\mathbf{D}^{(k)}} \mat{R}^{(2) \intercal} \mat{Q}^{(2) \intercal}$.
Thus, in order to calculate the SVD of $\ensuremath{\mathbf{A}}_k$, we would have to take the SVD of the
$R \times R$ matrix $\mat{R}^{(1)} \ensuremath{\mathbf{D}^{(k)}} \mat{R}^{(2) \intercal}$.
In the CP decomposition, slices $\mat{A}_k$
and $\ensuremath{\mathbf{A}}_{k'}$ may have different left and right singular vectors,
but these singular vectors are always in the span of
$\mat{Q}^{(1)}$ and $\mat{Q}^{(2)}$.
This flexibility allows \ref{eq:TVART}
to fit multiple linear models with different singular subspaces.

\subsection{Extensions: affine dynamics and higher-order autoregressions}

In many applications,
the mean of the data may drift over time,
and thus affine models of the dynamics
$\vec{x}(t+1) = \mat{A}_k \vec{x}(t) + \vec{b}_k$
are more appropriate than linear models
\citep{hirsh2019}.
We can fit an affine model of this type
within the TVART framework by appending a row
of ones to each $\mat{X}_k$
and extending $\U2$ by one row to build in a $\vec{b}_k$ term.
In this case, we have that
$\vec{b}_k = \U1 \ensuremath{\mathbf{D}^{(k)}} \vec{c}$,
where $\vec{c}$ is the extra row $\uvec2_{N+1,:}$.

Furthermore, autoregressive models of higher order are often considered,
where $\vec{x}(t+1)$ is predicted from data with $P$ lags
$\vec{x}(t), \ldots, \vec{x}(t - P + 1)$ \citep{west1997a,prado2000}.
In this case, the dimensions of $\ensuremath{\bm{\mathscr{X}}}$, $\ensuremath{\bm{\mathscr{A}}}$, and $\U2$ change
to $NP \times M \times T$, $N \times NP \times T$, and $NP \times R$,
respectively, but otherwise the mathematics remain equivalent.
For simplicity, we focus on just the $P = 1$ case,
but higher-order autoregressive models
are likely better-suited to certain applications.

\section{Alternating least squares algorithm}

\label{app:ALS}

We now describe in detail the optimization routine
used to solve \eqref{eq:TVART}.
Define the loss function to be
\begin{equation}
\label{eq:loss}
L \left( \U1, \U2, \U3 \right)  =
\frac{1}{2} \sum_{k=1}^T
\| \ensuremath{\mathbf{Y}}_k - \U1 \ensuremath{\mathbf{D}^{(k)}} {\U2}^\intercal \ensuremath{\mathbf{X}}_k \|_F^2 .
\end{equation}
Minimizing this loss
is an equivalent formulation of the TVART problem.
The loss \eqref{eq:loss} is quadratic and convex in each of the
variables $\U1, \U2$, and $\U3$,
but it is not jointly convex in all variables.
This motivates our use of an alternating minimization algorithm
to minimize this cost;
this is also called coordinate descent or,
since the loss is quadratic, alternating least squares (ALS).
Minimizing over any one of the $\U{i}$ is a least squares
problem that can be solved by a linear matrix equation.
In the next three subsections,
we compute the gradients of $L$ with respect to each set of variables
and discuss methods for solving the normal equations $\frac{\partial L}{\partial \U{i}} = 0$.
Alternating minimization is used in our final approach,
Algorithm~\ref{alg:alt-min},
which incorporates regularization.

We will use the following useful identity mutiple times:
\begin{align}
\frac{\partial}{\partial \mat{B}}
\frac{1}{2} \left\| \mat{Y} - \mat{A} \mat{B}^\intercal \mat{C} \right\|_F^2
&=
\frac{\partial}{\partial \mat{B}}
\frac{1}{2} \mathrm{Tr} \left[
\left( \mat{Y} - \mat{A} \mat{B}^\intercal \mat{C} \right)
\left( \mat{Y}^\intercal - \mat{C}^\intercal \mat{B} \mat{A}^\intercal \right)
\right]
\nonumber
\\
&=
-\mat{C} \mat{Y}^\intercal \mat{A} +
\mat{C} \mat{C}^\intercal \mat{B} \mat{A}^\intercal \mat{A} .
\label{eq:gradient_id}
\end{align}

\subsection{Left Spatial Modes $\U1$}

Taking partial derivatives of $L$ with respect to $\U1$,
we can employ \eqref{eq:gradient_id}
with
$
\mat{Y} \to \mat{Y}_k,
\mat{A} \to \mat{I},
\mat{C} \to \ensuremath{\mathbf{D}^{(k)}} \U2^\intercal \mat{X}_k
$
and
$\mat{B} \to \U1^\intercal$
and take the transpose to get
\begin{equation}
\label{eq:factor_1_ls}
\frac{\partial L}{\partial {\U1}}
=
\U1 \left( \sum_{k=1}^T
\ensuremath{\mathbf{D}^{(k)}} \U2^\intercal \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{X}}_k^\intercal \U2 \ensuremath{\mathbf{D}^{(k)}} \right)
-
\left( \sum_{k=1}^T
\ensuremath{\mathbf{Y}}_k \ensuremath{\mathbf{X}}_k^\intercal \U2 \ensuremath{\mathbf{D}^{(k)}} \right).
\end{equation}
Setting
$\frac{\partial L}{\partial {\U1}} = 0$
means we must solve
a matrix equation for $\U1$.
This requires forming an $N \times R$ matrix,
and right multiplying by the pseudoinverse of an $R \times R$ matrix.

\subsection{Right Spatial Modes $\U2$}

We now differentiate $L$ with respect to $\U2$.
Replacing
$
\mat{Y} \to \ensuremath{\mathbf{Y}}_k,
\mat{A} \to \U1 \ensuremath{\mathbf{D}^{(k)}},
\mat{C} \to \ensuremath{\mathbf{X}}_k$, and
$\mat{B} \to \U2$
in
\eqref{eq:gradient_id}
leads to the following:
\begin{equation}
  \label{eq:factor_2_ls}
  \frac{\partial L}{\partial {\U2}}
  =
  \sum_{k=1}^T \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{X}}_k^\intercal \, \U2 \, \ensuremath{\mathbf{D}^{(k)}} \U1^\intercal \U1 \ensuremath{\mathbf{D}^{(k)}}
  -
  \sum_{k=1}^T \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{Y}}_k^\intercal \U1 \ensuremath{\mathbf{D}^{(k)}},
\end{equation}
which we can rewrite in the form
\begin{equation}
\label{eq:grad_2}
  \frac{\partial L}{\partial {\U2}}
  =
  \sum_{k=1}^T \mat{L}_k \U2 \mat{R}_k
  - \mat{B},
\end{equation}
where
$\mathbf{B} \in \ensuremath{\mathbb{R}}^{N \times R}$,
$\mat{L}_k \in \ensuremath{\mathbb{R}}^{N \times N}$, and
$\mat{R}_k \in \ensuremath{\mathbb{R}}^{R \times R}$.

We set $\frac{\partial L}{\partial {\U2}} = 0$,
so that \eqref{eq:grad_2} implies a Sylvester equation
for the optimal $\U2$:
\begin{equation}
\label{eq:sylv}
  \frac{\partial L}{\partial {\U2}}
  =
  0
  \iff
  \sum_{k=1}^T \mat{L}_k \U2 \mat{R}_k
  = \mat{B} .
\end{equation}
For small $N$ and $R$,
we can use the Kronecker product $\otimes$ and vectorization operations to
rewrite \eqref{eq:sylv}
as a linear vector equation
\begin{equation}
  \label{eq:sylv_vec}
  \mathrm{vec}
  \left(
    \frac{\partial L}{\partial {\U2}}
  \right)
  = 0
  \iff
  \left( \sum_{k=1}^T \mat{R}_k^\intercal \otimes \mat{L}_k \right)
  \mathrm{vec} (\U2)
  =  \mathrm{vec} (\mathbf{B}).
\end{equation}
This is a square $NR \times NR$ linear system in $NR$ unknowns.
However, for large $N$, it is impractical to even form this matrix.
Therefore, we solve the Sylvester equation \eqref{eq:sylv}
via the matrix-valued method of conjugate gradients (CG).
Note that we do not need to form the $N \times N$ matrices
$\mat{L}_k = \mat{X}_k \mat{X}_k^\intercal$
to use matrix-free CG.

\subsection{Temporal Modes $\U3$}

Finally, we derive the gradients of $L$ with respect to $\U3$.
The equations for $\U3$, through which we define the $\ensuremath{\mathbf{D}^{(k)}}$,
are similar except in this case the unknown is a diagonal matrix.
The loss \eqref{eq:loss} with respect to $\ensuremath{\mathbf{D}^{(k)}}$ is decoupled across windows,
which leads to decoupled gradients as well.
Replacing
$
\mat{Y} \to \ensuremath{\mathbf{Y}}_k,
\mat{A} \to \U1,
\mat{C} \to \U2^\intercal \ensuremath{\mathbf{X}}_k$, and
$\mat{B} \to \ensuremath{\mathbf{D}^{(k)}}$
in
\eqref{eq:gradient_id}
leads to
\begin{align}
\frac{\partial L}{\partial {\ensuremath{\mathbf{D}^{(k)}}}}
&=
\left( \U2^\intercal \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{X}}_k^\intercal \U2
  \ensuremath{\mathbf{D}^{(k)}}
  \U1^\intercal \U1
-
\U2^\intercal \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{Y}}_k^\intercal \U1 \right) * \mathbf{I}
\nonumber \\
&=
\left( \mat{L}_k' \ensuremath{\mathbf{D}^{(k)}} \mat{R}_k' -
  \U2^\intercal \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{Y}}_k^\intercal \U1 \right) * \mathbf{I},
\label{eq:factor_3_grad}
\end{align}
where $*$ is the elementwise or Hadamard product,
which enforces the diagonal constraint on $\ensuremath{\mathbf{D}^{(k)}}$ and its gradient,
and
$\mat{L}_k' = \U2^\intercal \ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{X}}_k^\intercal \U2$ and
$\mat{R}_k' = \U1^\intercal \U1$
are $R \times R$ matrices.

By Theorem 2.5 in
\cite{million2007},
we have that
\[
 \left( \mat{L}_k' \ensuremath{\mathbf{D}^{(k)}} \mat{R}_k' \right)_{ii} =
 \left( (\mat{L}_k' * \mat{R}_k') \left( \uvec3_{k:} \right)^\intercal \right)_i,
\]
where we have substituted $\ensuremath{\mathbf{D}^{(k)}} = \mathrm{diag}(\uvec3_{k:})$.
Thus the gradient can be written as
\[
\mathrm{vecdiag}
\left(
\frac{\partial L}{\partial {\ensuremath{\mathbf{D}^{(k)}}}}
\right)
=
\left(\mat{L}_k' * \mat{R}_k' \right) \left( \uvec3_{k:} \right)^\intercal
-
\mathrm{vecdiag} \left( \U2^\intercal\ensuremath{\mathbf{X}}_k \ensuremath{\mathbf{Y}}_k^\intercal \U1 \right),
\]
where $\mathrm{vecdiag}(\mat{M})$ is the column vector formed
by the diagonal elements of $\mat{M}$.
Thus, the least-squares problem for $\U3$
involves solving an $R \times R$ system
for each row $\uvec3_{k:}$ of $\U3$ independently, $k = 1, \ldots, T$.
However, adding regularization to the temporal modes
destroys this decoupling across time windows,
which is why we resort to CG or proximal gradient approaches
in Algorithm~\ref{alg:alt-min}.

\subsection{Computational complexity of alternating least squares}

Each minimization step requires the solution of a linear matrix equation
$\frac{\partial L}{\partial \U{d}} = 0$
for $\U{d}$.
We now comment on the difficulty of solving the
subproblems in $\U1$, $\U2$, and $\U3$.
The subproblem in $\U1$ is by far the easiest,
since it involves just one $R \times R$ system solve
or pseudoinverse.
The subproblem in $\U3$ requires
$T$ decoupled $R \times R$ system solves.
The cost of this step is thus linear in $T$.
We assume that $R$ is small enough that solving for each
time window is fast.
By far the most difficult step
is the subproblem
for the right hand factors $\U2$.
This challenge is in part because we obtain a Sylvester equation
which we might naively solve using the Kronecker reformulation
as an $NR \times NR$ square system in $NR$ unknowns.
When we avoid using Kronecker products
and instead use matrix-free CG,
we can be assured that this will take less memory
but could take more time, depending on the condition number
of the Kronecker product matrix \eqref{eq:sylv_vec}.
However, in either case the subproblem involves
coefficient matrices of size $N$,
whereas for the other problems these are of size $R$.

\section{Regularization}
\label{sec:regularization}

Alternating least squares is a
natural approach to the \ref{eq:TVART}
problem as formulated.
However, we have found that ALS is numerically unstable
for the switching linear test problem (Sec.~\ref{sec:test_problem}).
This instability is worst with low or zero observation noise,
but it is alleviated when larger noise added to the data.
Additive, independent noise
adds a diagonal component to the data covariance,
which suggests we apply Tikhonov regularization to the problem.
An additional motivation for Tikhonov regularization
is that we do not want the entries in the matrices
$\U1$, $\U2$, and $\U3$ to become too large,
but some might become large
due to the scaling indeterminancy of the CP decomposition
\citep{kolda2009}.
We thus add a term
\begin{equation*}
\frac{1}{2 \eta} \left( \| \U1 \|_F^2 + \| \U2 \|_F^2 + \| \U3 \|_F^2 \right)
\end{equation*}
to the least-squares loss.
The parameter $\eta$ controls the magnitude of this Tikhonov regularization:
larger $\eta$ is a smaller penalty, and smaller $\eta$ is a stronger penalty.
In matrix completion problems, a similar two-term regularization
is often added and can be seen as a convex relaxation of the matrix rank.

\subsection{Temporal smoothing}

We also consider further regularization
of the temporal modes.
Recall that
the rows of $\U3$ correspond to the loadings at different time windows.
By forcing these rows to be correlated, we keep the system matrices $\mat{A}_k$
from varying too much from window to window, a form of temporal smoothing.
The first regularizer we consider is a total variation (TV) penalty:
\begin{equation}
  \label{eq:TV}
  \mathrm{TV} (\U3)
  = \sum_{r=1}^R \sum_{k=2}^{T} \big| u^{(3)}_{kr} - u^{(3)}_{k-1,r} \big|
  = \sum_{r=1}^R \| \mat{D} \, \uvec3_{:r} \|_1 .
\end{equation}
Matrix $\mat{D}$ is the $(T-1) \times T$ first difference matrix with free boundary conditions:
\begin{equation*}
  \mat{D} =
  \left[
    \begin{array}{rrrrrr}
      1 & -1 &  &  & \ldots  & 0 \\
       & 1 & -1 &  &  & \vdots \\
       &  & \ddots & \ddots & & \\
      \vdots &  &  & 1 & -1 &  \\
      0 & \ldots & &  & 1 & -1
    \end{array}
  \right].
\end{equation*}
TV prefers piecewise constant time components $\uvec3_{:r}$
since it penalizes nonzero first-differences with column-wise $\ell_1$
penalty $\| \cdot \|_1$ to enforce sparsity, appropriate for an SLDS.

Alternatively, we consider a spline penalty:
\begin{equation}
  \label{eq:spline}
  \mathrm{Spline} (\U3)
  = \frac{1}{2} \sum_{r=1}^R \sum_{k=2}^{T} \big( u^{(3)}_{kr} - u^{(3)}_{k-1,r} \big)^2
  = \frac{1}{2} \| \mat{D} \U3 \|_F^2.
\end{equation}
This linear smoother
penalizes the $\ell_2$-norm of the first derivative, leading to smoothly varying solutions.

\subsection{Regularized cost function}

We modify the problem \eqref{eq:TVART},
adding the Tikhonov and smoothing penalties
to the loss function.
These additions result in the regularized cost function
\begin{equation}
  \label{eq:TVART*}
  C =
  \frac{1}{2} \sum_{k=1}^T
  \| \ensuremath{\mathbf{Y}}_k - \ensuremath{\mathbf{A}}_k \ensuremath{\mathbf{X}}_k \|_F^2
  + \frac{1}{2 \eta} \left( \| \U1 \|_F^2 + \| \U2 \|_F^2 + \| \U3 \|_F^2 \right)
  +
  \beta \,
  \mathcal{R}( \U3 ),
  \tag{TVART*}
\end{equation}
where $\ensuremath{\mathbf{A}}_k$ follows equation \eqref{eq:slice_modes} as before.
Here,
$\mathcal{R} (\cdot)$ is either TV$(\cdot)$ or
Spline$(\cdot)$.
Increasing the temporal smoothing strength $\beta$
leads to stronger regularization, as does decreasing $\eta$.

\subsection{Alternating minimization algorithm}

\begin{algorithm}[t!]
\caption{Alternating minimization for \ref{eq:TVART*}}
\label{alg:alt-min}
\begin{algorithmic}[1]
\STATE{initialize
$\U1, \U2, \U3$ and
regularization parameters
$0 < \eta < \infty$,
$0 \leq \beta < \infty$ }
\REPEAT
\STATE{
$\U1 \leftarrow
\arg \min_{\mat{U}}
C \left( \mat{U}, \U2, \U3 \right)$
\hfill $R \times R$ linear system solve}
\STATE{
$\U2 \leftarrow
\arg \min_{\mat{U}}
C \left( \U1, \mat{U}, \U3 \right)$
\hfill
conjugate gradient}
\STATE{
$\U3 \leftarrow
\arg \min_{\mat{U}}
C \left( \U1, \U2, \mat{U} \right)$
\hfill
conjugate gradient (Spline)\\\hfill or proximal gradient (TV)}
\UNTIL{convergence criteria}
\RETURN{$\U1, \U2, \U3$}
\end{algorithmic}
\end{algorithm}

We solve the regularized problem \ref{eq:TVART*}
using alternating minimization,
also known as block coordinate descent,
detailed in Algorithm~\ref{alg:alt-min}.
The subroutines that minimize for $\U1, \U2$ and $\U3$
require different approaches.
Since the objective \ref{eq:TVART*} is quadratic
in $\U1$ and $\U2$,
we find these by solving a linear matrix equation
either directly or using CG;
CG works best for solving the Sylvester equation in $\U2$.
For $\U3$ with the Spline penalty, the cost is again quadratic so we also use CG.
However, the TV penalty is convex but not smooth, so in this case we use
the proximal gradient method with Nesterov acceleration \citep{beck2009}.

Algorithm~\ref{alg:alt-min}
has similar complexity to ALS for the unregularized problem.
However, in the regularized case the cost is dominated by
the minimization over $\U3$,
which requires computing the proximal operator
at each step of the proximal gradient method.

The following theorem proves that when Algorithm~\ref{alg:alt-min} converges,
it converges to a local minimum of the cost:
\begin{theorem}[Convergence of alternating minimization]
  \label{thm:convergence}
  For a convex regularizer $\mathcal{R}$,
  the sequence of iterates generated by
  Algorithm~\ref{alg:alt-min} is defined and bounded, and every cluster point is a
  coordinatewise minimum, i.e.\ a Nash point,
  of the regularized cost \ref{eq:TVART*}.
\end{theorem}
\begin{proof}
  We use the framework of \cite[][Theorem 5.1]{tseng2001}
  for cyclic block coordinate descent,
  of which Algorithm~\ref{alg:alt-min} is an example.
  This theorem requires objective functions with
  convex and lower semicontinuous blocks
  as well as bounded level sets.
  We split the cost into smooth and non-smooth parts
  \begin{equation*}
    \label{eq:cost_split}
    C (\U1, \U2, \U3) =
    f_0 (\U1, \U2, \U3) +
    f_1 (\U3) ,
  \end{equation*}
  where
  $f_1 (\U3) = \beta \mathcal{R}(\U3)$
  and $f_0$ contains the remaining loss and Tikhonov terms.
  The function $f_0$ is continuous and differentiable,
  and it is $\frac{1}{\eta}$-strongly convex in each of its blocks
  $\U1, \U2$, and $\U3$.
  However, $f_0$ is not a convex function.
  Also, $f_1$ is convex and continuous.
  Let $(\mat{U}_0^{(1)}, \mat{U}_0^{(2)}, \mat{U}_0^{(3)})$
  be the initialization
  and $a = C(\mat{U}_0^{(1)}, \mat{U}_0^{(2)}, \mat{U}_0^{(3)})$.
  Denote the level set
  \[
  S_a = \{(\U1, \U2, \U3): C (\U1, \U2, \U3) \leq a \}.
  \]
  Then, since
  $
  C(\U1, \U2, \U3) \geq
  \frac{1}{2\eta}
  \left( \| \U1 \|_F^2 + \| \U2 \|_F^2 + \| \U3 \|_F^2 \right)$
  and
  the ball
  $B_0(r) = \{x : \| \U1 \|_F^2 + \| \U2 \|_F^2 + \| \U3 \|_F^2 \leq r \}$
  is bounded,
  we can conclude that the level set
  $S_a \subseteq B_0(2\eta a)$
  is also bounded.
  Then by \cite[][Theorem 5.1]{tseng2001}, we obtain the result.
\end{proof}
\begin{remark}
  \label{remask_instability}
  We did not use any structure of $\mathcal{R}$ besides convexity
  and lower semicontinuity,
  thus the same convergence results hold for
  other regularizations with those properties.
  However, we did need to use the Tikhonov penalty to ensure
  that the level sets are bounded.
\end{remark}

\subsection{Implementation details}
\label{sec:alg_details}

The code and instructions for running it are available
from
\url{https://github.com/kharris/tvart}.
We implemented Algorithm~\ref{alg:alt-min} in MATLAB.
It was run on an
Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz, 1200 MHz
with 32 cores and 128 GB RAM
using Ubuntu 16.04.1 with Linux kernel 4.15.0-48-generic and
64-bit MATLAB R2017b.
The CG and prox-gradient subroutines are limited to 24 and 40 iterates,
respectively.
Proximal gradient uses a backtracking line search to find the step size
and the proximal operator of TV is evaluating using
{\tt prox\_tv1d} from UNLocBox \citep{perraudin2014}, and
this is typically the bottleneck step for large problems.
All hyperparameter tuning (for $R$, $M$, $\eta$, and $\beta$) was performed manually.

For initialization we use the following method.
We consider the entire timeseries
in two snapshot matrices,
\begin{equation*}
\ensuremath{\mathbf{X}} = \left[
  \begin{array}{cccc}
    \vert & \vert & & \vert \\
    \bm{x}(1) &\bm{x}(2) &\ldots &\bm{x}(T M) \\
    \vert & \vert & & \vert
  \end{array}
\right]
\quad \mbox{and} \quad
\ensuremath{\mathbf{Y}} = \left[
  \begin{array}{cccc}
    \vert & \vert & & \vert \\
    \bm{x}(2) &\bm{x}(3) &\ldots &\bm{x}(TM+1) \\
    \vert & \vert & & \vert
  \end{array}
\right] .
\end{equation*}
We then fit a single linear model to the timeseries
by
$\ensuremath{\mathbf{A}} = \ensuremath{\mathbf{Y}} \ensuremath{\mathbf{X}}^\dagger$ and form the matrices
$[ \mat{U}, \mat{S}, \mat{V} ] = \mathrm{svd}(\ensuremath{\mathbf{A}})$.
When $R = N$, the TVART modes are then initialized to
$\mat{U}_0^{(1)} = \mat{U}$,
$\mat{U}_0^{(2)} = \mat{V}$,
and
$\mat{U}_0^{(3)} = \vec{1}_T \vec{1}_R^\intercal/\sqrt{T}$ is
the matrix of all-ones with columns normalized.
If $R < N$, we truncate the smaller singular vectors,
and when $R > N$, we add columns equal to
$\vec{1}_N / \sqrt{N}$ to $\mat{U}_0^{(1)}$ and $\mat{U}_0^{(2)}$
and $\vec{1}_T/\sqrt{T}$ to $\mat{U}_0^{(3)}$.
Initializations with unequal columns appear to help speed up the initial phase
of the optimization, as opposed to all-ones.
For this reason, we add Gaussian noise to the initializations
with standard deviation $0.5 / \sqrt{N}$ to $\mat{U}_0^{(1)}$ and $\mat{U}_0^{(2)}$
and with standard deviation $0.5 / \sqrt{T}$ to $\mat{U}_0^{(3)}$.
Initializing to zeros is not appropriate since the gradients in that case
are always zero.
All of the results we present do not depend strongly on the realization of the noise.

For stopping criteria,
we use both a relative and absolute tolerance
on the decrease in the cost function.
Let $C_t$ be the cost of \ref{eq:TVART*} at iterate $t$.
Then, we stop if either
\begin{equation}
  \label{eq:convergence}
  \frac{|C_t - C_{t-1}|}{C_{t-1}} < {\tt rtol} \qquad {\rm or} \qquad |C_t - C_{t-1}| < {\tt atol}.
\end{equation}
Unless specified otherwise, {\tt rtol} = $10^{-4}$ and {\tt atol} = $10^{-6}$.
In all cases we have tested, the relative tolerance is acheived first.
We report the cost \ref{eq:TVART*} as it runs
as well as the root mean square error (RMSE),
which we define as:
\begin{equation}
  \label{eq:rmse}
  {\rm RMSE} = \sqrt{ \frac{1}{N M T} \sum_{k=1}^T \| \mat{Y}_k - \mat{A}_k \mat{X}_k \|_F^2} \, .
\end{equation}
The RMSE is normalized
so that it gives a measure of average one-step prediction error per channel.
This ``goodness of fit'' metric
can then be compared to the standard deviation of the data.

\section{Example applications}

In this section we test our method on both synthetic data and real-world datasets.
With synthetic data generated by a switching or smoothly varying linear dynamical system,
we show that TVART can recover
the true dynamics and is competitive with other state-of-the-art techniques.
In real-world data examples, we highlight how the recovered modes
are interpretable and can correspond to
important dynamical regimes.
For a complete list of the parameters used, please refer to Appendix~\ref{app:examples}.

\subsection{Test problem 1: switching low rank linear system}
\label{sec:test_problem}

\begin{figure}[t!]
  \centering

  \includegraphics[width=\linewidth]{switching-eps-converted-to.pdf}
  \caption{
    TVART correctly recovers the system matrices in a switching linear test problem.
    {\bf (Left, top)} Noisy observations input into the algorithm,
    where each line is one spatial measurement in time.
    Dashed lines denote the windows.
    {\bf (Left, bottom)}
    The temporal modes from TVART per window,
    which clearly pick out the change point at window 6.
    {\bf (Center)} We show the left and right spatial modes and
    the temporal modes output by TVART on the switching linear test case.
    Only four components are significantly different from zero.
    {\bf (Right)}
    In the top, we show the TVART estimate of the system matrix $\mat{A}_1$,
    the middle shows the truth, and the bottom shows their difference,
    which is relatively small. Colorbars are shared in the center and right columns.
  }
  \label{fig:test_case}
\end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width=0.6\linewidth]{switching_compare_err_2-eps-converted-to.pdf}

  \caption{TVART outperforms other methods on the switching test problem, for varying system size $N$.

  Average error of the inferred system matrix $\hat{\mat{A}}$ versus the true
  $\mat{A}$ measured in operator norm.

}
  \label{fig:test_comparison}
\end{figure}

\subsubsection{Model and data generation}

We first apply TVART to a simple test case
where the true model is a low rank,
switching linear system.
We generate two $N \times N$ system matrices
$\mat{A}_1$ and $\mat{A}_2$,
which are random, rank-2 rotation matrices.
For the first half of our timeseries, the dynamics follow
$\mat{A}_1$, and then they switch to $\mat{A}_2$.
Specifically, we form the matrices
$\mat{A}_i$ for $i=1, 2$ by the following process:
\begin{enumerate}
\item Generate a $2 \times 2$ rotation matrix
  $\mat{A}_i' = \left(
    \begin{array}{lr}
      \cos(\theta_i) & -\sin(\theta_i) \\
      \sin(\theta_i) & \cos(\theta_i)
    \end{array}
  \right)$.
\item Draw a random matrix $\mat{Z}_i \in \ensuremath{\mathbb{R}}^{N \times 2}$,
  with standard Gaussian entries.
\item Take the SVD:
  $[\mat{W}_i, \mat{S}_i, \mat{V}_i] = \mathrm{svd} (\mat{Z}_i) $.
\item Form a larger rotation matrix by projecting with onto the
  left singular vectors:
  $\mat{A}_i = \mat{W}_i \mat{A}_i' \mat{W}_i^\intercal$.
\end{enumerate}
Then, $\mat{A}_i$ is a random rotation matrix of rank 2.
We use $\theta_1 = 0.1\pi$ and $\theta_2 = 0.37 \pi$.

The trajectory is generated by starting with the initial condition
$\vec{x}(1) = \vec{1}$
and iterating 200 steps with $\mat{A}_1$ to remove a transient.
After the transient, the vector is renormalized to have $\|\vec{x}(t)\| = \sqrt{N}$.
For the first half of the timeseries $t < \tau/2$,
we iterate $\vec{x}(t+1) = \mat{A}_1 \, \vec{x}(t)$,
while for the second half $t \geq \tau/2$
we iterate $\vec{x}(t+1) = \mat{A}_2 \, \vec{x}(t)$.
After the first application of $\mat{A}_2$,
we again rescale $\vec{x}(t)$ to have norm $\sqrt{N}$.

After generating the noiseless trajectory,
we add independent, Gaussian observation noise
with standard deviation $\sigma$ to each entry of $\vec{x}(t)$.
Since the noise vector norm scales as $\sqrt{N}$, rescaling the signal vector by the
same factor allows us to maintain the same signal-to-noise ratio across different
system sizes $N$.
The RMSE of a model that is not overfit should be approximately $\sigma$ for any $N$.

\subsubsection{Performance of TVART}

We present results in
Figure~\ref{fig:test_case} for $N = 10$ and $\sigma=0.5$.
The TVART algorithm is run with
$M=20$, $R = 8$, $\eta = 1/N$,
$\beta = 5$, and TV regularization.
Algorithm~\ref{alg:alt-min} converges in 30 iterations
with an RMSE of 0.554, which is close
to the noise floor $\sigma = 0.5$.
The temporal modes are stable for the first 5
windows, when system $\mat{A}_1$ is active,
then switch to a different state for the remaining windows
where $\mat{A}_2$ is active.
Thus just from the temporal modes, we can determine the change point
to the resolution of the window size.
Examining the TVART output in more detail,
only the first four
spatial and temporal modes are significantly different from 0.
Remarkably, TVART is able to discover the true rank of the system;
this is 4 because $\mat{A}_1$ and $\mat{A}_2$ are each rank 2.
Furthermore, we compare the TVART reconstruction of $\mat{A}_1$
to the truth; the reconstruction matches the truth very closely
(Figure~\ref{fig:test_case}).

We now describe some other behaviors that have been observed
in this test problem for parameters that are not shown.
When the noise $\sigma$ is very small or zero,
the Tikhonov regularization term is important.
If we eliminate this term by taking $\eta \to \infty$,
the ALS subproblems become ill-conditioned and lead to poor results.
Without the Tikhonov penalty,
the true rank of the system is also less obvious---the
entries which are nearly 0 in Figure~\ref{fig:test_case} are noisier---whereas
the penalty shrinks these noisy entries.
The TV regularization, in contrast,
is important for selecting a switching solution under moderate to large noise.

\subsubsection{Comparison to other methods}

We compared TVART method to two alternative approaches:
independent windowed fits using multivariate regression,
for a simple baseline,
as well as a Bayesian SLDS fit using the
{\tt ssm} package available from
\url{https://github.com/slinderman/ssm}.

The independent model is tested with full rank and
rank truncation to 4 or 6, using the SVD.
To fit a rank $R<N$ model on the $k$th window of data,
we first perform the SVD on the entire $k$th timeseries,
fit a linear model for the $R$ leading temporal modes,
and project back into the $N$-dimensional space using the spatial modes.

The SLDS fit was allowed 6000 iterations and
performed with either a 4 or 6 dimensional latent space
with the maximum number of switches parameter set to {\tt Kmax} = 4
and otherwise default parameter values.

For TVART we use a rank of either 4 or 6 and the parameters
$M=20, \eta = 1/N$, $\beta = 1$, and TV regularization.
Recall that the true rank of the system is 4.

In Figure~\ref{fig:test_comparison},
we show the results as we sweep across system sizes
$N$ from 10 to 4000.
We depict the error in the reconstruction
$\| \mat{A} - \hat{\mat{A}} \|_2$ averaged across all time windows.
Note that if we measure the entrywise error in the reconstruction,
this decreases with $N$, whereas the operator norm error is constant;
the relative trends remain the same in any norm.
We see that TVART of either rank is able to recover the true dynamics $\mat{A}$
better than any of the other methods.
SLDS performs worse but slightly better than independent for rank 4,
rank 6 is similar,
although both degrades for higher system sizes $N$.
TVART is also much faster than SLDS, by roughly an order of magnitude.

These results are with the current version of \texttt{ssm} with the default settings.
A previous version of this package with similar settings did perform better
(results are shown in an earlier version of this paper, available at
\url{https://arxiv.org/abs/1905.08389v1}).
However, in that case, TVART was still as good or better than the alternative methods
while running much faster.
We conclude that TVART with TV regularization
is a scalable, alternative way of finding low rank switching linear dynamics.

\subsection{Test problem 2: smoothly varying low rank linear system}

\subsubsection{Model and data generation}

Another comparison was made by assuming rank 2 orthogonal dynamics that are {\em smooth}.
In the previous switching linear example, the dynamics were generated from
a rotation matrix for two different angles $\theta_1$ and $\theta_2$.
In this case, the angle
$\theta(t)$ comes from a smooth Gaussian process
in order to have slowly-varying rank 2 dynamics.
In this case, the orthogonal projection into the higher space $\mat{W}$ is
fixed for all time.

In detail, we form a different system matrix at each time step $t$ by
\begin{equation*}
  \mat{A}(t) =
  \mat{W}
  \left(
    \begin{array}{lr}
      \cos(\theta(t)) & -\sin(\theta(t)) \\
      \sin(\theta(t)) & \cos(\theta(t))
    \end{array}
  \right)
   \mat{W}^\intercal ,
\end{equation*}
where the random basis $\mat{W}$ is drawn as before.
The angle $\theta(t)$ is from a centered Gaussian process
with covariance function
\begin{equation*}
  K(t,t') =
  \exp \left[
    -\left(\frac{t - t'}{30}\right)^2
  \right]
  +
  0.001 \,\delta_{t,t'} .
\end{equation*}
This squared exponential covariance produces smooth trajectories $\theta(t)$
that are approximately constant over the timescale of $\sim 30$ time steps.
The small diagonal covariance ensures numerical stability of the Cholesky decomposition.
We add Gaussian observation noise with standard deviation $\sigma = 0.2$.

\subsubsection{Results}

We depict the data for a realization with $N=10$ in Figure~\ref{fig:test_case_2}.
This includes the angle $\theta(t)$ drawn from the Gaussian process and
observations of the dynamical system output.
It is clear that the frequency of oscillations in the state variables
are stable over short timescales, but that the frequency is modulated as $\theta(t)$ changes.

TVART is applied to these data with $R=4$,
$M = 1$,
$\eta = 6 / N$,
and $\beta = 600 \, \log_{10}^2 (N)$ with the Spline regularization.
The temporal modes are shown as well as a comparison of
$\mat{A}(t)$ versus the inferred $\hat{\mat{A}}(t)$
at $t=1$.
Interestingly, with these values of regularization,
we can fit an accurate model at every time point without overfitting.
The recovered system is effectively rank 3 selected by the Tikhonov penalty.

We also tested the method for other values of $N$ varying between 6 and 4000.
The results are not shown, but the performance of TVART is stable
across system sizes, with $\| \mat{A} - \hat{\mat{A}} \|_2 \approx 0.1$.
Independent fits perform significantly worse, and SLDS is even poorer.
This is not surprising, since an independent model is sure to overfit while
the SLDS model is inherently not smooth and thus highly biased.

\begin{figure}[t!]
  \centering

  \includegraphics[width=0.59\linewidth,trim={0cm .5cm 0cm .2cm},clip]{smooth_summary-eps-converted-to.pdf}
  \hspace{.5cm}
  \includegraphics[width=0.25\linewidth]{smooth_matrices-eps-converted-to.pdf}

  \caption{
    Smoothly varying linear test case.
    {\bf (Left, top)} The rotation angle trajectory $\theta(t)$ drawn from
    the Gaussian process.
    {\bf (Left, middle)} State variable observations for an example fit with $N = 10$.
    {\bf (Left, bottom)} The temporal fit with the parameters described in the text.
    For the strong temporal regularization used,
    we can fit an accurate model at every time point.
    {\bf (Right)} Comparing the inferred matrix and the truth for the first timestep
    $t = 1$.}
  \label{fig:test_case_2}
\end{figure}

\subsection{Dataset 1: worm behavior}

\begin{figure}[t]
  \centering
  \includegraphics[width=.6\linewidth,trim={1.2cm 1cm 1.3cm 1cm},clip]{example_worms-eps-converted-to.pdf}
  \caption{TVART applied to the worm behavior dataset.
    In this example, the worm begins moving forward, executes a turn,
    and continues but in the backward direction.
    The temporal modes in TVART are able to pick out these three regimes,
    and a clustering of them identifies these three behavioral states.
  }
  \label{fig:worms}
\end{figure}

We analyze the escape response behavior of the nematode worm
{\it Caenorhabditis elegans}
in response to a heat stimulus \citep{broekmans2016a,broekmans2016}.
These were used as test data for clustering via adaptive linear models
in the recent work of \cite{costa2019}.
Worm postural data were analyzed as smooth timeseries of
$N = 4$
``eigenworm'' principal components.
We ran TVART with an affine model and $R=6, M=6, \eta = 0.05$, and $\beta = 6$ on these data.
We also compared the performance of the code provided by \cite{costa2019}
at \url{https://github.com/AntonioCCosta/local-linear-segmentation}.

The results for worm 1 are shown in Figure~\ref{fig:worms}.
We performed clustering on the system matrices as before with three clusters
and found that these clusters matched the three behaviors in the data:
forward crawling, a turn, and backward crawling.
These clusters are not trivial:
the data means during forward and backward motion are approximately equal,
but the phase velocity switches.

Finally, we also compared our results to the code provided by
\cite{costa2019}, which fits an adaptive linear model and clusters the same timeseries;
the clustering results are essentially the same.
In terms of runtime, fitting a TVART model, performing clustering, and displaying the results
takes 23 s (90 iterates), versus 123 s for the code of \cite{costa2019}.
Thus, we see that our method is much faster than theirs,
while producing essentially the same clustering results.

\subsection{Dataset 2: sea surface temperature}

\begin{figure}[t]
  \centering
  \includegraphics[width=0.6\linewidth,trim={1cm 2cm 1.5cm .1cm},clip]{example_el_nino_mode_5-eps-converted-to.pdf}
  \caption{Mode corresponding to the ENSO
    (El Ni\~no/Southern Oscillation) climate pattern
    found with TVART.
    ENSO is associated with warm water in the equatorial Pacific Ocean.
  }
  \label{fig:sst}
\end{figure}

We applied our method to weekly sea surface
temperature data from 1990 until present
\citep{reynolds2002}.
Sea surface temperature data contain oscillations with varying timescales,
from seasonal to multi-decadal.
This is also a very high-dimensional test for the TVART algorithm.

Weekly sea surface temperature grids
were downsampled by a factor of 6 in the latitudinal
and longitudinal directions,
resulting in final vectors of length $N = 1259$.
We chose a window size of $M = 9$ weeks,
resulting in $T = 171$ windows, and use parameters $\eta = 10^{-3}$, $\beta = 10^4$,
and the Spline regularizer.
Using our standard initialization, the ALS routine stagnates
as the matrix $\U2$ converges very slowly.
However, we have found that restarting the algorithm after 10 iterations
and setting $\U2 = \U1$ in the new initialization speeds things up significantly.
This heuristic was inspired by the fact that the solution has $\U2 \approx \U1$.
In the end, the algorithm requires 1176 iterations to converge.

The leading modes that are output by the algorithm oscillate seasonally.
However, we also find that mode 5, as ordered by $\ell_2$ energy, tracks
the El Ni\~{n}o-Southern Oscillation (ENSO), Figure~\ref{fig:sst}.
The corresponding spatial modes show a plume of warm water in the
central and eastern equatorial Pacific Ocean.
Warmer than average water in this location is the signature of ENSO.
Thus, TVART is able to discover an important dynamical feature in a large spatiotemporal dataset.

\subsection{Dataset 3: neural activity during a reaching task}

\begin{figure}[t]
  \centering
  \includegraphics[width=0.6\linewidth,trim={1cm 1cm 1cm .5cm},clip]{neurotycho_clusters-eps-converted-to.pdf}
  \caption{TVART applied to neural activity (ECoG) data captures movements.
    The dynamical clusters inferred by our method approximately correspond
    to movement and rest states.
  }
  \label{fig:monkey}
\end{figure}

A second high-dimensional dataset comes from
electrocorticography recordings
(ECoG)
of a Japanese macaque monkey {\it Macaca fuscata}
during a reaching task, provided by the NeuroTycho project \citep{chao2010}.
This is an invasive technology that measures brain activity
using chronic electrodes placed below the skull and the dura mater.
During the task, the monkey makes repeated reaches towards food while its limbs
are tracked using motion capture and brain activity is recorded.

We analyzed the data of monkey K1, date 2009-05-25.
We ran TVART on the $N=64$ channel
ECoG voltage data after filtering out 50 Hz line noise,
downsampling to 500 Hz,
and standardization.
The TVART parameters were
$M = 200$, $R = 8$, $\eta = 1$, $\beta = 100$, and TV regularization,
resulting in $T = 1999$ windows of length 0.4 s.

Figure~\ref{fig:monkey} depicts the results:
We show motion capture data with dashed lines at the onset and offsets of
movements, using a changepoint detection procedure.
We also highlight the result of clustering the TVART temporal modes,
obtained from the brain activity alone, into two clusters.
The brain activity reveals two dominant modes, one of which is aligned to movement.
These movements are accompanied by an increase in high frequency (32-200 Hz)
and a decrease in low frequency (2-32 Hz) power.
The dominant TVART mode (show in blue) follows this spectral change in the timeseries.
TVART tracks this spectral change directly from the timeseries of electrode voltage.
Furthermore, the spatial modes associated with it are centered in the premotor region,
as depicted in Figure~\ref{fig:monkey_mode}.
Again, we observe that an important spatiotemporal feature has been extracted via
the TVART algorithm.

\begin{figure}[t]
  \centering
  \includegraphics[width=0.9\linewidth]{neurotycho_mode_summary-eps-converted-to.pdf}
  \caption{The dominant spatial modes (left and right) of TVART applied to the neural activity dataset.
    In the left mode, the electrodes with largest weight are centered in the premotor region
    known to be active during reaching,
    posterior of the arcuate sulcus and more medial than lateral.
    The right spatial mode is less interpretable.
    Data and brain images provided by NeuroTycho project \citep{chao2010}.
  }
  \label{fig:monkey_mode}
\end{figure}

\section{Conclusions}

We have presented a low rank tensor formulation of dynamical linear modeling
that we call {\it time-varying autoregression with low rank tensors}, or TVART.
Our method offers the advantage of being able to scale to problems
with many state variables or many time points,
as highlighted by our examples.
It also allows for incorporating prior knowledge of the temporal
structure of the dynamics via regularization,
which can lead to more stable and accurate reconstructions from less data.
We have shown that enforcing different kinds of temporal smoothness aids
in the identification of switching or slowly-varying dynamics.
We have also shown that TVART can be used with a variety of real datasets,
and the modes output by our method are often interpretable
as dominant dynamical features in the data.

There are limitations to TVART.
First, it has a number of hyperparameters,
such as the latent rank, stopping tolerances, and regularization strengths,
that must be tuned to the problem at hand.
While our method is generally more scalable than Bayesian approaches,
it suffers from fragility to hyperparameter choice.
In our experiments, it seems that with true underlying linear dynamics
(i.e.\ in the synthetic test cases),
good results with rapid convergence may be obtained using a wide range of parameters.
On real datasets, tuning these took more effort, although here we limited our tuning
to the reuglarization parameters $\eta$ and $\beta$.

A second limitation is the potential sensitivity of TVART to initialization.
Due to non-convexity, there is no guarantee that Algorithm~\ref{alg:alt-min} converges
to a global optimum.
In our experiments, we only found problems with this in the SST and ECoG datasets,
and adding noise to the initialization helped find better solutions.
We have verified that our results hold qualitatively across multiple random initializations,
as is standard with other tensor decompositions \citep{kolda2009}.
This is our recommended approach.

Finally, we have noted that the convergence sometimes stagnates for large problems,
in particular the SST and ECoG datasets.
This seems to affect the right spatial modes $\U2$ more severely than the others.
This may be due to the use of matrix-valued CG for that subproblem,
but it also seems likely that the subproblem for the right spatial modes
is inherently more ill-conditioned with correlated data.
Multiresolution methods \citep{park2020} or explicit regularization of spatial modes
could improve convergence and produce more interpretable results
with large and spatially-correlated datasets.

Future work with TVART should investigate these and other possible extensions.
Higher-order autoregressive models \citep{west1997},
which incorporate multiple time delays stacked into Hankel matrices \citep{takens1981,gibson1992},
are a natural next step which would allow
for wider applications, e.g.\ to economic data.
Theoretically, it would be good to have more understanding of what linear models
of nonlinear dynamics precisely find.
It has recently been proven that some other non-convex factorization problems
have no spurious local minima \citep[e.g.][]{ge2017}.
Thus, it would be interesting to know whether there may exist similar results for
properly constrained CP decomposition models.
This might lead to modified versions of TVART with guaranteed optimality.

\section*{Acknowledgements}

Thank you to Scott Linderman and Nathan Kutz for discussions
and to Steven Peterson for help preprocessing the NeuroTycho data.
KDH was supported by a Washington Research Foundation Postdoctoral Fellowship.
BWB, RR, and KDH were supported by NSF CNS award 1630178 and
DARPA award FA8750-18-2-025.

{\small
\setlength{\bibsep}{0pt plus 0.3ex}
\bibliographystyle{siamplain}