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

\IEEEPARstart{L}{ow-level} computer vision problems such as denoising, demosaicing or super-resolution can be formalised as inverse problems and approached with modern machine learning techniques: a degraded input is processed by a convolutional neural network (CNN) trained in a supervised way to produce a restored output. The input is typically a single frame~\cite{zhang2017beyond,brooks2019unprocessing,gharbi2016deep,kokkinos2019jdd,lim2017enhanced,dai2019second}---but significantly better results can be obtained by leveraging the temporal redundancy of sequential images~\cite{liu2014fast,jo2018deep,wang2019edvr,godard2018deep,frvsr,fuoli2019efficient}. There are two main categories of video processing CNNs. \emph{Feedforward models} operate in a sliding-window fashion and process mutliple frames jointly to produce a current output. \emph{Recurrent models} operate in a frame-by-frame fashion but have the ability to store information internally through feedback loops. Recurrent processing is appealing because it reuses information efficiently, potentially over a large number of frames. At the same time, Recurrent Neural Networks (RNNs) are dynamical systems that can exhibit complex and even chaotic behaviors~\cite{laurent2016recurrent}. In the context of sequence modelling for language or sound understanding for instance, RNNs are known to suffer from vanishing and exploding gradient issues at training time~\cite{pascanu2013difficulty}, and to be vulnerable to instabilities through positive feedback at inference time~\cite{miller2019stable}.

\subsection{Motivation}
\label{sec:Motivation}

In the context of video processing, recurrent CNNs are typically trained on short video sequences of up to 10 frames \cite{frvsr,godard2018deep,fuoli2019efficient}. \emph{At inference time,} they can be applied to sequences of arbitrary length---but it has been observed before that they sometimes suffer from instabilities on long video sequences~\cite{godard2018deep}. To illustrate this phenomenon, we retrain the video denoiser of~\cite{godard2018deep} on the \mbox{Vimeo-90k} dataset~\cite{xue2019video} and we evaluate it on $4$ sequences of $1600$ frames (i.e. roughly one minute of video at $24$ fps) downloaded from vimeo.com. We plot the performance of the model measured by the peak-signal-to-noise-ratio (PSNR) as a function of the frame number and we observe instabilities on all $4$ sequences: the PSNR plunges suddenly and permanently at some unpredictable time in the sequence. Visually, these instabilities correspond to the formation of colorful artifacts at random locations, growing locally until the entire output frame is covered. Numerically, they correspond to diverging or saturating pixel values (see Figure~\ref{instabilities}).

\begin{figure*}[ht]
\begin{center}
\subfloat{\includegraphics[width=\textwidth]{figures/instabilities_psnr.pdf}}
\vspace{0.1cm}
\subfloat{\includegraphics[width=\textwidth]{figures/instabilities_outputs.pdf}}
\end{center}
\caption{The recurrent video denoiser from \cite{godard2018deep} is applied to four sequences of $1600$ frames downloaded from vimeo.com. Above: The PSNR per frame is stable for a number of frames varying between $200$ and $1500$, before plunging below $0$ on all $4$ sequences (indicated by red stars). Below: The performance drop manifests itself in the form of strong colorful artifacts and black masks on the output image (see also Appendix~A).}
\label{instabilities}
\end{figure*}

Our working hypothesis is that recurrent connections create positive feedback loops prone to this type of divergent behaviour. As a proof of concept, we consider a backbone architecture made of five convolutional layers interleaved with ReLU non-linearities, and we augment it with various strategies for temporal processing. We consider single-frame and multi-frame inputs, and four types of temporal connections inspired from existing video processing works: feature-shifting~\cite{huang2015bidirectional,lin2019tsm}, feature-recurrence~\cite{huang2015bidirectional,chen2016deep,godard2018deep}, frame-recurrence~\cite{frvsr,arias2019kalman} and recurrent latent space propagation (RLSP)~\cite{fuoli2019efficient} (see Figure~\ref{random_models_architectures}). We then initialize all the models randomly and feed them with random inputs. We see that feedforward architectures (single-frame, multi-frame, feature-shifting) produce stable outputs while recurrent architectures (feature-recurrence, frame-recurrence, RLSP) produce outputs that diverge (see Figure~\ref{random_models_plots}). Note that feature-shifting is non-recurrent since, while information is temporally delayed, it is not fed back to the same processing block multiple times.

\begin{figure*}[ht]
\begin{center}
\subfloat[From left to right: feature-shifting~\cite{huang2015bidirectional,lin2019tsm}, feature-recurrence~\cite{huang2015bidirectional,chen2016deep,godard2018deep}, frame-recurrence~\cite{frvsr,arias2019kalman}, RLSP~\cite{fuoli2019efficient}.\label{random_models_architectures}]{%
\includegraphics[width=0.48\textwidth]{figures/random_models_architectures.pdf}
}
\hfill
\subfloat[Norm of the output frame over a random sequence of 50 frames, for six architectures initialized with a Gaussian distribution $(\sigma=0.1)$.\label{random_models_plots}]{%
\includegraphics[width=0.48\textwidth]{figures/random_models_plots.pdf}
}
\end{center}
\caption{For untrained models over random inputs, feedforward architectures produce stable outputs (single-frame, multi-frame, feature-shifting) while recurrent architectures diverge (frame-recurrence, feature-recurrence, RLSP).}
\label{random_models}
\end{figure*}

The instabilities described above are a serious concern for the deployment of recurrent video processing models in the real world. If catastrophic failures occur at unpredictable times in the sequence, affected models cannot be trusted, even on relatively short sequences. In fact, determining whether a given model is affected or not is already problematic: there is no guarantee \emph{a priori} that a model that behaves in a stable manner on a set of video sequences will remain stable on all video sequences.

\subsection{Contributions}

The main contributions of this paper can be summarized as follows:
\begin{itemize}
    \item We identify and characterize a serious vulnerability affecting recurrent networks for video processing: they can be unstable at inference time and fail catastrophically on long video sequences.
    \item To test stability, we introduce a fast and reliable diagnostic tool that produces adversarial input sequences optimized to trigger instabilities, and that can be interpreted as spatio-temporal receptive fields.
    \item We investigate two approaches to enforce the stability of recurrent video processing networks: constraining the spectral norm or constraining the stable rank of their convolutional layers.
    \item We extend a recently proposed weight normalization scheme called Stable Rank Normalization (SRN)~\cite{sanyal2020stable} that simultaneously constrains the spectral norm and the stable rank of any linear mapping, to convolutional layers. We call it Stable Rank Normalization of the Layer (SRNL)---as opposed to stable rank normalization applied to the convolutional kernel.
\end{itemize}

\subsection{Related Work}

A number of approaches have been proposed in the literature for extending the connectivity of a CNN in the time domain. In~\cite{karpathy2014large}, the authors identify three classes of feedforward models: \emph{early fusion} where the frames over a fixed time window are concatenated and processed simultaneously, \emph{late fusion} where the frames are processed independently and their latent space representations are concatenated at a later stage, and \emph{slow fusion} where intermediary features are concatenated at multiple levels such that higher layers get access to progressively more global information in both spatial and temporal dimensions. Variants of slow fusion were introduced a number times under different names: \emph{conditional convolutions} in~\cite{huang2015bidirectional}, \emph{3D~convolutions} in~\cite{tran2015learning}, \emph{progressive fusion} in~\cite{yi2019progressive} and \emph{feature-shifting} in~\cite{lin2019tsm} all fuse features from different time steps at multiple levels of the network. For video restoration tasks, most standard models implement a form of early fusion~\cite{liu2014fast,caballero2017real,jo2018deep,mildenhall2018burst,wang2019edvr} but late fusion~\cite{tassano2019dvdnet} and two-level fusion~\cite{tassano2020fastdvdnet} have also been used occasionally.

In contrast with the feedforward fusion approaches above, recurrent models contain feedback loops where the features are extracted at a layer $l_1$ at time $t-1$ and fed back at a lower layer $l_2 < l_1$ at time $t$. To the best of our knowledge, a recurrent CNN was first applied to a video restoration task in~\cite{huang2015bidirectional}. The architecture proposed for video super-resolution used a heavy set of temporal connections, with forward ($x_{t-1} \to x_t \to x_{t+1}$) and backward ($x_{t+1} \to x_t \to x_{t-1}$) subnetworks, each using both \emph{conditional} and \emph{recurrent} connections corresponding to \emph{feature-shifting} and \emph{feature-recurrence} respectively according to our taxonomy from Figure~\ref{random_models_architectures}. Feature recurrence was used again for video denoising in~\cite{chen2016deep} on a deep but non-convolutional RNN, and in~\cite{godard2018deep} on the multi-frame branch of a hybrid architecture constituted of a single-frame denoiser and a multi-frame denoiser. Frame-recurrence, where the previous output frame is fed back as an additional input at the next time step, was introduced for video super-resolution in~\cite{frvsr}. This type of recurrence was studied further in~\cite{arias2019kalman} where a connection was made with the concept of Kalman filtering~\cite{kalman1960new}. Recently and still in super-resolution, recurrent latent space propagation (RLSP) was introduced~\cite{fuoli2019efficient}. RLSP can be interpreted as maximizing the depth and width of the recurrent connection, compared to feature-recurrence and frame-recurrence. Iterative approaches~\cite{irani1991improving,zamir2017feedback,haris2018deep,haris2019recurrent} are conceptually similar to recurrent ones, but the feedback loop is part of a refinement mechanism that occurs for a fixed number of iterations, chosen as a hyperparameter by the user independently of the temporal length of the video sequence. Long Short-Term Memory (LSTM)~\cite{hochreiter1997long} is a type of gated RNN that is compatible with convolutions and has been used for video description and captioning~\cite{donahue2015long,yu2016video,johnson2016densecap} but rarely for video restoration~\cite{tao2017detail}. In this paper, we focus on standard recurrent architectures in their three variants: feature-recurrence, frame-recurrence and RLSP.

Training Recurrent Neural Networks (RNNs) is notoriously difficult due to the \emph{vanishing and exploding gradients} problem: RNNs are trained by unrolling through time, which is effectively equivalent to training a very deep network~\cite{bengio1994learning,pascanu2013difficulty}. Relatedly, \emph{RNNs are vulnerable to instabilities at inference time on long sequences}. This phenomenon was studied in the context of 1-layer fully connected networks in~\cite{jin1994absolute}, and in the context of multi-layer and LSTM networks in~\cite{miller2019stable}, where it was shown that the RNN is stable if its Lipschitz constant is less than~$1$. In~\cite{miller2019stable}, it was proposed to enforce this stability constraint by projecting onto the spectral norm ball of the recurrence matrix (i.e. by clipping its singular values to 1) and a number of recent works have sought to avoid vanishing and exploding gradients by enforcing orthogonality (i.e. setting all the singular values to 1)~\cite{arjovsky2016unitary,wisdom2016full,mhammedi2017efficient,vorontsov2017orthogonality,jose2018kronecker,zhang2018stabilizing}. In the context of convolutional neural networks however, enforcing the Lipschitz constraint is challenging. In~\cite{sedghi2019singular}, it was proposed to clip singular values of the convolutional (but non-recurrent) layer, which was flattened into a matrix using the doubly block circulant matrix representation. However, the optimization method does not have formal convergence guarantees and requires computing all singular values of the flattened kernel. In~\cite{miyato2018spectral}, it was proposed to normalize the kernel of the convolutional (but non-recurrent) layer during training, the $4$-D kernel being first reshaped into a \mbox{$2$-D} matrix by flattening its first three dimensions. Normalization is performed by an elegant iterative scheme employing the power iteration estimating the maximal singular value of the flattened kernel. However, as discussed in~\cite{scaman2018lipschitz} and~\cite{gouk2018regularisation}, this approach is not suitable for Lipschitz regularization due to the invalid flattening operation used, and as a result is not suitable for stability enforcement using~\cite{miller2019stable} either. To solve this issue, Gouk et al.~\cite{gouk2018regularisation} suggested replacing the \mbox{$2$-D} matrix products in the power iteration with convolution and transpose convolution operations using the \mbox{$4$-D} kernel tensor directly. This method was applied with success in \cite{behrmann2019invertible} to train invertible ResNets.

Recently, Sanyal et al. (2020)~\cite{sanyal2020stable} proposed Stable Rank Normalization (SRN), a provably optimal weight normalization scheme which minimizes the stable rank of a linear operator while constraining the spectral norm. They showed that SRN, while improving the classification accuracy, also improves generalization of neural networks and reduces memorization. However, SRN operates on a 2-D reshaping of the convolutional kernel, instead of operating on the convolutional layer as a whole.

\section{Stability in recurrent video processing}

In this section, we mathematically define the notion of stability. We then introduce the Spatio-Temporal Receptive Field (STRF) diagnostic tool and the two stability constraints, before presenting our Stable Rank Normalization of the Layers algorithm.

\subsection{Definitions}
\label{sec:Definitions}

Partially reusing notations from~\cite{miller2019stable}, we define a recurrent video processing model as a non-linear dynamical system given by a Lipschitz continuous \emph{recurrence map} \mbox{$\phi_w : \mathbb{R}^n \times \mathbb{R}^d \to \mathbb{R}^n$} and an \emph{output map} $\psi_w : \mathbb{R}^n \to \mathbb{R}^d$ parameterized by $w \in \mathbb{R}^m$. The hidden state $h_t \in \mathbb{R}^n$ and the output image $y_t \in \mathbb{R}^d$ evolve in discrete time steps according to the update rule\footnote{The case where $y_t = h_t$ corresponds to the frame-recurrent architecture of~\cite{frvsr}.}
\begin{equation}
\begin{cases}
  h_t &= \phi_w(h_{t-1}, x_t)\\
  y_t &= \psi_w(h_t)
\end{cases}
\end{equation}
where the vector $x_t \in [0,1]^d$ is an arbitrary input image provided to the system at time~$t$.

In Section~\ref{sec:Motivation}, we showed examples of models that produced diverging outputs and called them ``unstable''. In the following, we propose to use the notion \emph{Bounded-Input Bounded-Output (BIBO) stability}.
\begin{defn}\label{def:stability}
A recurrent video processing model is \emph{BIBO stable} if, for any admissible input $\{x_t\}_{t= 0}^\infty$ for which there exist a constant $C_1$ such that $\sup_{t\ge 0}\|x_t\|\le C_1$, there exists a constant $C_2$ such that $\sup_{t\ge 0}\|y_t\|\le C_2$.
\end{defn}
This definition is well suited for models using ReLU activation functions, and the diagnostic tool we introduce in the next section relies on it. However, it fails to capture a stricter notion of stability for models with bounded activation functions, which are BIBO stable by construction\footnote{Simply applying a sigmoid function to the output of an unstable model technically makes it BIBO stable, yet in practice, the model still suffers from instabilities and its output simply saturates.}. Therefore, we will use the stricter notion of \emph{Lipschitz stability} for stability enforcement, as in~\cite{miller2019stable}.
\begin{defn}\label{def:contractiveness}
A recurrent video processing model is \emph{Lipschitz stable} if its recurrence map $\phi_w$ is \emph{contractive in $h$}, i.e. if there exists a constant $L<1$ such that, for any states $h, h^\prime\in \R^n$ and input $x \in \R^d$,
\begin{equation}
    \| \phi_w(h, x) - \phi_w(h^\prime, x)\| \leq L \| h - h^\prime \|.
\end{equation}
\end{defn}
The constant $L$ is called the Lipschitz constant of $\phi_w$. We show easily that Lipschitz stability implies BIBO stability, but the reciprocal is not always true.

\subsection{Diagnosis}
\label{sec:Diagnosis}

Consider a \emph{trained} recurrent video processing model $(\phi_w,\psi_w)$. Proving that it is \emph{BIBO unstable} can be easy: one simply needs to find an \emph{unstable sequence}, i.e. an input sequence $\{x_t\}_{t= 0}^\infty$ such that the corresponding output sequence $\{y_t\}_{t= 0}^\infty$ diverges. Proving that the model is \emph{BIBO stable}, however, is hard: one needs to perform an exhaustive search over the (infinite) set of valid inputs, and check that none of them are unstable. Alternatively, one could try to show that the model is \emph{Lipschitz stable} instead. Unfortunately, computing the Lipschitz constant for a neural network is, in general, NP-hard~\cite{scaman2018lipschitz}.

In practice, one realistic approach is to run the model on a very long video sequence and observe possible instabilities---effectively performing a \emph{random search} for unstable sequences over the set of valid inputs---but it is not clear which video sequence should be used and how long the search should last before one can reliably conclude that the recurrent model is, indeed, stable. As Figure~\ref{instabilities} shows, this is not a trivial question: instabilities do not occur after the same number of frames on all video sequences and it can easily take more than a thousand frames before an instability occurs. At the same time, guaranteeing stability is a fundamental safety concern in any real-world deployment.

Here, we propose to approach the problem in a different way and to \emph{search for unstable sequence by gradient descent}. We fix a sequence length $2\tau + 1$ and an image size $d$, and also consider the finite input sequence $X = (x_{-\tau}, ..., x_{\tau})$ with the corresponding finite output sequence $Y = (y_{-\tau}, ..., y_{\tau})$ such that, for all $t \in [-\tau,\tau]$:
\begin{alignat*}{2}
&h_{-\tau-1} = 0 &\qquad& \text{The initial hidden state is null}\\
&h_t = \phi_w(x_t, h_{t-1}) &      & \text{$\phi_w,$ is unrolled over the sequence}\\
&y_t = \psi_w(h_t) &      & \text{$\psi_w$ maps to the output image}
\end{alignat*}
And we search for unstable sequences by optimizing:
\begin{equation}\label{adv-sequence}
\max_{0 \leq X \leq 1} \;\; \mathcal{L}(Y)
\end{equation}
where $\mathcal{L}$ is a chosen objective function on the output sequence. We consider in particular the following two cases.
\begin{itemize}
    \item When $\mathcal{L}(Y) = \|y_0\|$, the optimization problem~(\ref{adv-sequence}) consists in finding an input sequence $X$ such that the corresponding output sequence $Y$ diverges maximally at time $t=0$. Since this optimization process only affects the \emph{frames} in $X$ that have an effect on $y_0$, the resulting input sequence $X$ can be interpreted as a visualization of the \emph{Temporal Receptive Field} for the output frame at time $t=0$.
    \item When $\mathcal{L}(Y) = |p|$ where $p$ is the pixel in the centre of $y_0$, optimizing the problem~(\ref{adv-sequence}) only affects the \emph{pixels} in $X$ that have an effect on the value of $p$, and hence, the resulting input sequence $X$ can be interpreted as a visualization of the \emph{Spatio-Temporal Receptive Field} for the output pixel $p$.
\end{itemize}
This type of optimization on the output of a model with regards to its input is inspired from the research on \emph{adversarial examples} in image classification~\cite{szegedy2014intriguing,goodfellow2015explaining,kurakin2017adversarial,ilyas2019adversarial,biggio2018wild} and an unstable sequence $X$ can be viewed as an \emph{adversarial sequence}. It has also been used for \emph{feature visualization} before~\cite{erhan2009visualizing,szegedy2014intriguing,mahendran2015understanding,nguyen2015deep,olah2017feature}, although never in the context of recurrent networks to the best of our knowledge. In practice, we initialise $X$ randomly, we choose a sequence length $\tau = 40$ and an image size $d = 64 \times 64$. We then solve the optimization problem using the Adam optimizer for 1000 iterations. We iterate multiple times to avoid vanishing gradient issues but we found experimentally that the number of iterations does not need to be very high.

Computing the Spatio-Temporal Receptive Field (STRF) of a given model can then be used as a diagnostic tool for its stability, and we observe two possible behaviours.
\begin{itemize}
\item \textbf{The STRF is not temporally bounded.} Input frames in the distant past have an effect on $p$ and output frames in the distant future diverge (see Figure~\ref{unstable-STRF}). The input sequence $X$ constitutes an unstable sequence and we can conclude with certainty that the model is unstable.
\item \textbf{The STRF is temporally bounded.} Input frames in the distant past have no effect on $p$ and output frames in the distant future remain unaffected (see Figure~\ref{stable-STRF}). No unstable sequence has been found and we can conclude with reasonable confidence that the model is stable.
\end{itemize}
Running the model on 2h30m of video (random search) and computing the STRF (gradient descent search) cannot constitute formal proofs of stability, but we show in the experimental section that they give consistent answers on the stability of various models. STRFs also help visualize the temporal window of influence of a model, or how long information can stay in memory, and therefore illustrates the relationship between stability and memory in RNNs.

\begin{figure*}
\centering
\subfloat[STRF of an unstable model. The receptive field is not temporally bounded and the output sequence $Y$ diverges. \label{unstable-STRF}]{%
\thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.6 cm} \thead{\makebox[\ws cm]{\raggedleft $-40$} \makebox[\ws cm]{$-30$} \makebox[\ws cm]{$-20$} \makebox[\ws cm]{$-10$} \makebox[\ws cm]{$0$} \makebox[\ws cm]{$+10$} \makebox[\ws cm]{$+20$} \makebox[\ws cm]{$+30$} \makebox[\ws cm]{\raggedright $+40$}\\ \includegraphics[width=0.95\textwidth, height=1.29cm]{figures/VResNet-feat-SRNL-20-04_TRF_long.png}}}

\subfloat[STRF of a stable model. The receptive field is temporally bounded ($\approx 17$ frames) and the output sequence $Y$ is well-behaved. \label{stable-STRF}]{%
\thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.6 cm} \thead{\makebox[\ws cm]{\raggedleft $-40$} \makebox[\ws cm]{$-30$} \makebox[\ws cm]{$-20$} \makebox[\ws cm]{$-10$} \makebox[\ws cm]{$0$} \makebox[\ws cm]{$+10$} \makebox[\ws cm]{$+20$} \makebox[\ws cm]{$+30$} \makebox[\ws cm]{\raggedright $+40$}\\ \includegraphics[width=0.95\textwidth, height=1.29cm]{figures/VResNet-feat-SNL-10_TRF_long.png}}}
\caption{Spatio-Temporal Receptive Field (STRF) as a diagnostic tool. The input sequence $X$ is optimized to trigger instabilities in the output sequence~$Y$ (here we use $\mathcal{L}(Y) = |p|$). The sequences have been horizontally compressed to fit the page width. In the rest of the paper, we plot the STRFs every 5 frames for convenience, but the optimization is always performed on sequences of 81 frames as $\tau = 40$.}
\end{figure*}

\subsection{Prevention}

Now, consider an \emph{untrained} recurrent video processing model $(\phi_w,\psi_w)$. In order to prevent instabilities from occuring at inference time, we want to enforce a stability constraint into the model at training time. As discussed in Section~\ref{sec:Definitions}, this can be achieved by ensuring that $\phi_w$ is contractive with respect to the recurrent variable.

Suppose that $\phi_w$ is made of $l$ convolutional layers separated by ReLU non-linearities. Each convolution can be represented by its 4D kernel tensors ${\bm K}$, or by a corresponding 2D matrix ${\bm W}$ obtained from ${\bm K}$ as a block matrix of doubly-block-circulant matrices~\cite{sedghi2019singular}. Then for a layer ${\bm W}$ with singular values $\{\sigma_k\}$ assumed to be sorted, the spectral norm is $\|{\bm W}\| = \sigma_1$, the Frobenius norm is $\|{\bm W}\|_F = \sqrt{\sum_k \sigma_k^2}$ and the \emph{stable rank}\footnote{The stable rank is a soft, numerical approximation of the rank operator. It is \emph{stable} under small perturbations of the matrix---the name has nothing to do \emph{a priori} with the notion of stability studied here.} is defined as~\cite{rudelson2007sampling,sanyal2020stable}:
\begin{equation}
    \text{srank}({\bm W}) = \frac{\|{\bm W}\|_F^2}{\|{\bm W}\|^2} = \frac{\sum_k \sigma_k^2}{\sigma_1^2}.
\end{equation}
It is a scale independent quantity and can be interpreted as an \emph{area-under-the-curve} for the normalized singular value spectrum. Now, let $L$ be the Lipschitz constant of $\phi_w$. Since the Lipschitz constant of the ReLU non-linearity is~1, we know that $L$ is upper-bounded by the product of the spectral norms of the linear layers~\cite{scaman2018lipschitz,szegedy2014intriguing}.
\begin{prop}
For a recurrent model $\phi_w$ constituted of $l$ linear layers with weight matrices ${\bm W}_1, ..., {\bm W}_l \in \mathbb{R}^{n\times n}$ interspaced with ReLU non-linearities, the Lipschitz constant $L$ of $\phi_w$ satisfies:
\begin{equation}\label{eq:Lipschitz-upper-bound}
    L \leq \prod_{i=1}^l \|{\bm W}_i\|.
\end{equation}
\end{prop}
Using this upper-bound, one can guarantee that $\phi_w$ is contractive (i.e. $L < 1$) with the following approach.
\begin{appr}
\textbf{Hard Lipschitz Constraint}\nopagebreak

\noindent For all $i \in [1,l]$, we enforce $\|{\bm W}_i\| < 1$.
\end{appr}
This approach has the advantage of providing a theoretical guarantee of stability. However, it is overly restrictive because the upper-bound~(\ref{eq:Lipschitz-upper-bound}) tends to significantly overestimate the Lipschitz constant $L$~\cite{sanyal2020stable}. To illustrate why this is the case, suppose that $\phi_w$ contains two layers ${\bm W}_1$ and ${\bm W}_2$. Then the only situation in which we have $L = \|{\bm W}_1\| \|{\bm W}_2\|$ is when the first right singular vector of ${\bm W}_1$ is aligned with the first left singular vector of ${\bm W}_2$. In other situations, $L$ depends on the rest of the singular value spectra of ${\bm W}_1$ and ${\bm W}_2$ and hence, on their stable ranks. These considerations lead us to a second approach to enforce $L < 1$.
\begin{appr}
\textbf{Soft Lipschitz Constraint}\nopagebreak

\noindent For all $i \in [1,l]$, we fix $\|{\bm W}_i\| = \alpha$ and minimize $\text{\normalfont srank}({\bm W}_i)$.
\end{appr}
This approach does not offer any theoretical guarantee of stability for $\alpha > 1$. However, we verify empirically in Section~\ref{sec:Experiments} that it is also successful at promoting stability.

\begin{figure*}
\noindent
\begin{minipage}[t]{0.49\textwidth}
\let\@latex@error\@gobble
\begin{algorithm}[H]
\DontPrintSemicolon
\KwIn{Number of iterations $N$, learning rate $\eta$,\;
\hspace{1cm} number of channels $m$, image size $n$,\;
\hspace{1cm} initial ${\bm K} \in \mathbb{R}^{k\times k\times m \times m}$, initial ${\bm u} \in \mathbb{R}^m$.}
\Parameter{Spectral norm $\alpha$, stable rank $\beta$.}
\nonl \Begin{
    \nonl \For{$i=1,\dots, N$}{
    $\widetilde{{\bm K}} = \text{Reshape}({\bm K},[k k m,m])^\textrm{T}$\;
    \nonl \emph{Power iteration:}\;
    ${\bm v}   =  \widetilde{{\bm K}}^\textrm{T} {\bm u}/ \|\widetilde{{\bm K}}^\textrm{T} {\bm u}\|_2$\;
    ${\bm u}   =  \widetilde{{\bm K}} {\bm v}/ \|\widetilde{{\bm K}} {\bm v}\|_2$\;
    \nonl \emph{Spectral normalization:}\;
    $\widetilde{{\bm K}}  = \widetilde{{\bm K}}/({\bm u}^\textrm{T} (\widetilde{{\bm K}} {\bm v}) +\varepsilon)$\;
    \nonl \emph{Stable rank ($\beta < 1$):}\;
    ${\bm S}_1 = {\bm u}{\bm v}^\textrm{T}$\;
    ${\bm S}_2 = \widetilde{{\bm K}} - {\bm S}_1$\;
    $\gamma = \sqrt{\beta m - 1}/ \|{\bm S}_2\|_F$\;
    \If{$\gamma < 1$}{
    \nonl $\widetilde{{\bm K}} = {\bm S}_1 + \gamma{\bm S}_2$
    }
    \mbox{$\widetilde{{\bm K}} = \text{Reshape}(\widetilde{{\bm K}}^\textrm{T},[k,k,m,m])$}\\
    \nonl \emph{Training step:}\;
    ${\bm K}  = {\bm K} - \eta \nabla_{\bm K} L(\alpha \,\widetilde{{\bm K}})$
   }
}
\caption{\emph{SRN--$\alpha$--$\beta$} (Sanyal et al. (2020)~\cite{sanyal2020stable})} \label{alg-SRN}
\end{algorithm}
\end{minipage}
\hfill
\begin{minipage}[t]{0.49\textwidth}
\let\@latex@error\@gobble
\begin{algorithm}[H]
\DontPrintSemicolon
\KwIn{Number of iterations $N$, learning rate $\eta$,\;
\hspace{1cm} number of channels $m$, image size $n$,\;
\hspace{1cm} initial ${\bm K} \in \mathbb{R}^{k\times k\times m \times m}$, initial ${\bm u} \in \mathbb{R}^{n \times n \times m}$.}
\Parameter{Spectral norm $\alpha$, stable rank $\beta$.}
\nonl \Begin{
    \nonl \For{$i=1,\dots, N$}{
    $\widetilde{{\bm K}} = {\bm K}$\;
    \nonl \emph{Power iteration:}\;
    ${\bm v}   =  \widetilde{{\bm K}}^\textrm{T} \ast {\bm u}/ \|\widetilde{{\bm K}}^\textrm{T} \ast {\bm u}\|_2$\;
    ${\bm u}   =  \widetilde{{\bm K}} \ast {\bm v}/ \|\widetilde{{\bm K}} \ast {\bm v}\|_2$\;
    \nonl \emph{Spectral normalization:}\;
    $\widetilde{{\bm K}}  = \widetilde{{\bm K}}/({\bm u}^\textrm{T} (\widetilde{{\bm K}} \ast {\bm v}) +\varepsilon)$\;
    \nonl \emph{Stable rank ($\beta < 1$):}\;
    ${\bm S}_1 = \nabla_{\widetilde{{\bm K}}}( {\bm u}^\textrm{T} (\widetilde{{\bm K}} \ast {\bm v}))$\;
    ${\bm S}_2 = \widetilde{{\bm K}} - {\bm S}_1$\;
    $\gamma = \sqrt{\beta m - 1/n^2}/ \|{\bm S}_2\|_F$\;
    \If{$\gamma < 1$}{
    \nonl $\widetilde{{\bm K}} = {\bm S}_1 + \gamma{\bm S}_2$
    }
    \phantom{abc}\;
    \nonl \emph{Training step:}\;
    ${\bm K}  = {\bm K} - \eta \nabla_{\bm K} L(\alpha \,\widetilde{{\bm K}})$
   }
}
\caption{\emph{SRNL--$\alpha$--$\beta$} ({\bf Our})} \label{alg-SRNL}
\end{algorithm}
\end{minipage}
\end{figure*}

\subsection{Stable rank normalization of the layers}

A couple of tools have been proposed before to enforce the constraints of Approaches~1 and~2. \emph{Spectral normalization} (SN), introduced by Miyato et al.~\cite{miyato2018spectral} and popularized in GAN training~\cite{zhang2019self,brock2019large}, allows one to fix the spectral norm of convolutional layers to a desired value $\alpha$. \emph{Stable rank normalization} (SRN), introduced by Sanyal et al.~\cite{sanyal2020stable}, builds on top of the previous work and allows one to also control the stable rank with a parameter $\beta \in [0,1]$ (see Algorithm~\ref{alg-SRN}). However, as observed before in~\cite{scaman2018lipschitz,gouk2018regularisation}, there is an issue with SN and by extension with SRN: they operate on a 2D reshaping of the kernel tensor ${\bm K}$, instead of operating on the matrix of the convolutional layer ${\bm W}$. At the same time, operating on ${\bm W}$ directly is impossible: the matrix is too large to be expressed explicitly\footnote{For a kernel size $k$, a number of input and output channels $m$ and an image size $n$, the dimension of ${\bm K}$ is $[k, k, m, m]$ (typically around $10^3$ parameters) while the dimension of ${\bm W}$ is $[n n m, n n m]$ (typically around $10^{13}$ sparse parameters).}. Below, we introduce a version of SRN that operates on ${\bm W}$ indirectly, using ${\bm K}$. To distinguish between the two versions, we refer to our algorithm as \emph{Stable Rank Normalization of the Layer} or SRNL (see Algorithm~\ref{alg-SRNL}).

The two algorithms are structurally identical---they consist in a power iteration to compute the spectral norm (steps 2,3), a normalization (step 4) and a re-weighting of a rank one matrix ${\bm S}_1$ and a residual matrix ${\bm S}_2$ (steps 5, 6, 7, 8)---but they present a number of key differences. In SRNL, the random vector ${\bm u}$ has two more dimensions and is the size of a full input feature map ($[1, n, n, m]$). The kernel is not flattened (steps~1, 9). The power iteration is performed using a convolution ($\widetilde{{\bm K}} \ast \;\cdot$) and a transposed convolution ($\widetilde{{\bm K}}^\textrm{T} \ast \;\cdot$) as suggested in~\cite{gouk2018regularisation}, based on the observations that:
\begin{equation}
\begin{split}
{\bm v}   =  \widetilde{{\bm W}}^\textrm{T} {\bm u} \quad &\Leftrightarrow \quad {\bm v}   =  \widetilde{{\bm K}}^\textrm{T} \ast {\bm u} \quad \text{(step 2)} \quad \text{and}\\
{\bm u}   =  \widetilde{{\bm W}} {\bm v} \quad &\Leftrightarrow \quad {\bm u}   =  \widetilde{{\bm K}} \ast {\bm v} \quad \text{(step 3)}.
\end{split}
\end{equation}
The spectral normalization is also performed using a convolution (step~4). The rank one matrix ${\bm S}_1 = {\bm u}{\bm v}^\textrm{T}$ is expressed as a 4D kernel tensor through the gradient of ${\bm u}^\textrm{T} (\widetilde{{\bm K}} \ast {\bm v})$ with respect to $\widetilde{{\bm K}}$ (step~5), based on the observation that:
\begin{equation}
{\bm u} {\bm v}^\textrm{T} = \nabla_{\widetilde{{\bm W}}}(\text{trace}(\widetilde{{\bm W}} {\bm v} {\bm u}^\textrm{T})) = \nabla_{\widetilde{{\bm W}}}({\bm u}^\textrm{T} \widetilde{{\bm W}} {\bm v}).
\end{equation}
Finally, writing $\|\widetilde{{\bm W}}\|_F$ explicitly yields $\|\widetilde{{\bm W}}\|_F = n \|\widetilde{{\bm K}}\|_F$ and therefore (step 7):
\begin{equation}
\gamma = \frac{\sqrt{\beta n n m - 1}}{n \|{\bm S}_2\|_F} = \frac{\sqrt{\beta m - 1/n^2}}{\|{\bm S}_2\|_F}.
\end{equation}

When $\beta = 1$, SRN and SRNL are equivalent to performing spectral normalization on ${\bm K}$ and ${\bm W}$ respectively.
When $\beta < 1$, they also have an effect on the stable rank of their respective matrices. We found experimentally that SRN multiplies the training time by a factor of $\approx 1.8$ and SRNL multiplies the training time by a factor of $\approx 2.2$. At inference time, the weights are fixed and normalized convolutions have the same complexity as standard convolutions.

\section{Experiments}
\label{sec:Experiments}

In this section, we illustrate our diagnostic tool on a number of video denoising models trained in a standard way without constraints. We then show that our stable rank normalization algorithm successfully enforces stability via the two approaches discussed.

\subsection{Unconstrained Models}
\label{sec:Unconstrained Models}

To reflect the variety of architectures used for video processing tasks, we consider two backbone networks and three types of recurrence. The two backbone networks consist in a DnCNN-like~\cite{zhang2017beyond} stack of 10 convolutions and ReLU non-linearities (VDnCNN), and a ResNet-like~\cite{he2016deep} stack of 5 residual blocks containing two convolutions each separated by a ReLU (VResNet). The three types of recurrences are the ones considered in Section~\ref{sec:Motivation}, namely, feature-recurrence~\cite{huang2015bidirectional,chen2016deep,godard2018deep}, frame-recurrence~\cite{frvsr,arias2019kalman} and recurrent latent space propagation (RLSP)~\cite{fuoli2019efficient}. More architectural details are provided in Figure~\ref{network_architectures}.

\begin{figure}[ht]
\begin{center}
\subfloat[VDnCNN \label{VDnCNN}]{\includegraphics[width=0.45\textwidth]{figures/VDnCNN.pdf}}
\vspace{-0.2cm}
\subfloat[VResNet \label{VResNet}]{\includegraphics[width=0.45\textwidth]{figures/VResNet.pdf}}
\vspace{-0.2cm}
\subfloat{\includegraphics[width=0.45\textwidth]{figures/building_blocks.pdf}}
\end{center}
\caption{The two architectures and three types of recurrence considered.}
\label{network_architectures}
\end{figure}

Here, we chose to focus on video denoising and keep the evaluation of other video processing tasks for future work. We train our models using the Vimeo-90k septuplet dataset \cite{xue2019video}, consisting of about 90k 7-frame RGB sequences with a resolution of $448 \times 256$ downloaded from vimeo.com. We generate clean-noisy training pairs by applying Gaussian noise with standard deviation $\sigma = 30$. The recurrent networks are trained using backpropagation through time on sequences of 7 frames---making use of the full length of the Vimeo-90k sequences---on image crops of $64 \times 64$ pixels. We train using the Adam optimizer with a batch size of 32 for 600k steps. For comparison, we also consider the traditional non-recurrent methods BM3D~\cite{dabov2007image} and VNLB~\cite{arias2015towards} and the recurrent deep burst denoising network of~\cite{godard2018deep}, which we refer to as DBDNet and retrain in the same conditions as the other recurrent models. In Table~\ref{table:PSNRs}, we show the numbers of parameters and processing speeds\footnote{We use the authors' implementations of BM3D (Matlab) and VNLB (C++). All our recurrent networks are implemented in TensorFlow. The processing speeds are indicative of an order of magnitude only.} (fps) of each method, as well as their denoising performances as measured by the PSNR on the first frame ($\text{PSNR}_1$), last frame ($\text{PSNR}_7$) and averaged over all the frames ($\text{PSNR}_{\text{mean}}$) on the first 1024 validation sequences of the Vimeo-90k septuplet dataset. Since BM3D processes sequences frame by frame, VNLB processes sequences all at once, and recurrent networks reuse information from one frame to the next, the performance of BM3D is flat over each sequence, it peaks on the median frame for VNLB and it peaks on the last frame for recurrent networks. VNLB outperforms other methods on average, but recurrent models have a higher PSNR on the seventh frame, and they are orders of magnitude faster to run. The performance on the last frame ($\text{PSNR}_7$) is of special interest as it can be regarded as an approximation of the plateaued performance of an online video denoiser applied to a very long sequence. For that reason, we focus on this metric in the rest of the paper. Among the different recurrent models, the VResNet backbone systematically outperforms the \mbox{VDnCNN} one, possibly partly because VDnCNN is slower to converge. Frame-recurrent architectures are the lightest and fastest, but feature-recurrence and RLSP yield better performance. Interestingly, VResNet-RLSP has about $60\%$ less parameters than DBDNet~\cite{godard2018deep}, is significantly faster and performs better ($+0.33$dB on $\text{PSNR}_7$).

\setlength{\tabcolsep}{3pt}
\begin{table}
\begin{center}
\caption{Size, processing speed and performance of the different video denoising methods considered, measured on the first frame ($\text{PSNR}_1$), last frame ($\text{PSNR}_7$), and averaged over all the frames ($\text{PSNR}_{\text{mean}}$) on the Vimeo-90k septuplet dataset.}
\label{table:PSNRs}
\begin{tabular}{lccccc}
\hline
\noalign{\smallskip}
  & \# param. & fps & $\text{PSNR}_1$ & $\text{PSNR}_7$ & $\text{PSNR}_{\text{mean}}$ \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
BM3D~\cite{dabov2007image} & n/a & 2 & 33.86 & 33.83 & 33.85\\
VNLB~\cite{arias2015towards} & n/a & $0.02$ & \textbf{35.24} & 35.17 & \textbf{35.78}\\
DBDNet~\cite{godard2018deep} & 965k & 30 & 34.16 & 35.47 & 35.16\\
VDnCNN-frame & \textbf{375k} & \textbf{70} & 33.94 & 34.84 & 34.68\\
VDnCNN-feat & 741k & 40 & 34.05 & 35.02 & 34.79\\
VDnCNN-RLSP & 410k & 60 & 33.95 & 34.98 & 34.77\\
VResNet-frame & \textbf{375k} & \textbf{70} & 34.23 & 35.47 & 35.21\\
VResNet-feat & 557k & 50 & 34.35 & \textbf{35.74} & 35.41\\
VResNet-RLSP & 410k & 60 & 34.25 & \textbf{35.80} & 35.42\\
\hline
\end{tabular}
\end{center}
\end{table}

\setlength{\tabcolsep}{3pt}
\begin{table*}[ht]
\centering
\caption{Instabilities in 6 models with 2 backbone architectures and 3 types of recurrences. For each model, we show the performance on the 7th frame of the Vimeo-90k validation dataset ($\text{PSNR}_7$), the $1^{st}$ and $9^{th}$ deciles of the instability onsets on a sequence of about 2h30min ($\infty$ means no instabilities observed). We also show the singular value spectrum averaged over the convolutions of the model, computed using the code from~\cite{sedghi2019singular}, and the temporal receptive field computed using our method.}
\label{table:unconstrained_models}
\begin{tabular}{|c|ccc|}
\hline
 model & \thead{$\text{PSNR}_7$\\ $1^{st}$ dec.\\ $9^{th}$ dec.} & \thead{Average\\ Singular Value\\Spectrum} & Spatio-Temporal Receptive Field \\
\hline
\thead{VDnCNN\\--frame} & \thead{$34.84$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VDnCNN-frame_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VDnCNN-frame_TRF.png}} \\
\thead{VDnCNN\\--feat} & \thead{$35.02$\\$157$\\$5709$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VDnCNN-feat2_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VDnCNN-feat2_TRF.png}} \\
\thead{VDnCNN\\--RLSP} & \thead{$34.98$\\$74$\\$271$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VDnCNN-RLSP_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VDnCNN-RLSP_TRF.png}} \\
\thead{VResNet\\--frame} & \thead{$35.47$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-frame_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-frame_TRF.png}} \\
\thead{VResNet\\--feat} & \thead{$35.74$\\$29$\\$75$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat_TRF.png}} \\
\thead{VResNet\\--RLSP} & \thead{$35.80$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-RLSP_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-RLSP_TRF.png}} \\
\hline
\end{tabular}
\end{table*}

To evaluate the stability of each recurrent model, we apply them to one long video sequence lasting approximately 2h30m consisting of several clips downloaded from vimeo.com and concatenated together ($2\times 10^5$ frames). Each time the PSNR drops below 0, we consider that an instability occurs and we \emph{reset} the recurrent features to~0. We call \emph{instability onset} the number of frames leading to an instability. In Table~\ref{table:unconstrained_models}, we report the $1^{st}$ and $9^{th}$ decile of the instability onsets for each model ($\infty$ means no instability observed). According to this test, VDnCNN-frame, VResNet-frame and VResNet-RLSP are stable while VDnCNN-feat, VDnCNN-RLSP and VResNet-feat are unstable. For VDnCNN-feat in particular, the instability onset is above 5709 frames in 10\% of the cases, highlighting the necessity to run this test on very long video sequences. We show examples of output sequences for the 3 unstable models in Appendix~A. In an attempt at explaining why certain models are stable and others are not, we compute the singular value spectra of all their convolutional layers using the code provided by Sedghi et al. in~\cite{sedghi2019singular}---this gives us access to their spectral norms in particular, or maximum singular value (leftmost value in each spectrum). Unfortunately, the spectra all have comparable profiles and are therefore uninformative, with spectral norms typically around 6: too high to conclude anything about the contractiveness of the recurrent maps using the upper-bound~(\ref{eq:Lipschitz-upper-bound}). Finally, we compute the spatio-temporal receptive fields of each model using the approach described in Section~\ref{sec:Diagnosis}. In accordance with the previous test, VDnCNN-feat, VDnCNN-RLSP and VResNet-feat exhibit the characteristic behaviour of unstable models, with long-range temporal dependencies accumulating in the input sequences $X$, resulting in unstable output sequences $Y$ diverging at frame $+40$. The spatio-temporal receptive fields of VDnCNN-frame, VResNet-frame and VResNet-RLSP on the other hand, are well-behaved: the information flow is limited to a finite temporal window, input frames in the distant past have no influence on the current frame and future output frames do not diverge. Frame-recurrent models appear to have a short temporal receptive field ($\approx 10$ frames) compared to other models, possibly making this type of recurrence more stable in practice.

\subsection{Constrained models}

We saw in the previous section that various models with different backbone architectures and types of recurrence trained in standard conditions are unstable on long video sequences at inference time. We have also discussed in the introduction how the instabilities observed constitute catastrophic failures that are a serious concern for real-world deployment. Now, we show that inference-time stability can be enforced during training, with the help of our \emph{stable rank normalization of the layers} algorithm (SRNL). We focus on the VResNet-feat architecture, as it appeared to be the most vulnerable to instabilities with 80\% of the onsets happening between 29 and 75 frames only.

First, let us consider the model trained with \mbox{SRN-1.0-1.0} in the first line of Table~\ref{table:constrained_models}. According to the average singular value spectrum computed using the code from~\cite{sedghi2019singular}, its convolutional layers have spectral norms that are significantly larger than~$1$ at around~$2.5$, and which vary significantly ($\pm 0.2$). This observation confirms that normalizing a 2D reshaping of the convolutional kernel ${\bm K}$ is a poor approximation of normalizing the convolutional layer ${\bm W}$: SRN fails to set the spectral norm of ${\bm W}$ to the desired value $\alpha$ and this motivates the introduction of SRNL.

Now, let us consider the models trained with \mbox{SRNL-$\alpha$-1.0} for $\alpha \in \{2.0, 1.5, 1.0, 0.5\}$ in lines~2 to 5 of Table~\ref{table:constrained_models}. As expected, the spectral norms of all the convolutional layers are now precisely set to their respective values of $\alpha$. Our test on the long video sequence and our spatio-temporal receptive field diagnostic then show that the models trained with $\alpha > 1$ are unstable while the models trained with $\alpha < 1$ are stable. This observation confirms that our Hard Lipschitz Constraint is effective at enforcing stability. Interestingly, reducing $\alpha < 1$ shortens the temporal length of the receptive field, a side effect of the recurrence map becoming more contractive. However, reducing $\alpha$ also hurts performance, as measured by the $\text{PSNR}_7$ ($-0.4$dB from $\alpha = 2.0$ to $\alpha = 1.0$), and this motivates the introduction of the Soft Lipschitz Constraint.

\setlength{\tabcolsep}{3pt}
\begin{table*}[p]
\centering
\caption{SRN and SRNL with different values of $\alpha$ and $\beta$ on VResNet-feat. For each model, we show the performance on the 7th frame of the Vimeo-90k validation dataset ($\text{PSNR}_7$), the $1^{st}$ and $9^{th}$ deciles of the instability onsets on a sequence of about 2h30min ($\infty$ means no instabilities observed). We also show the singular value spectrum averaged over the convolutions of the model, computed using the code from~\cite{sedghi2019singular}, and the temporal receptive field computed using our method.}
\label{table:constrained_models}
\begin{tabular}{|c|ccc|}
\hline
 model & \thead{$\text{PSNR}_7$\\ $1^{st}$ dec.\\ $9^{th}$ dec.} & \thead{Average\\ Singular Value\\Spectrum} & Spatio-Temporal Receptive Field \\
\hline
\thead{SRN\\$\alpha=1.0$\\$\beta=1.0$} & \thead{$35.64$\\$69$\\$295$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SNK-1.0_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SNK-1.0_TRF.png}}\\
\hline
\thead{SRNL\\$\boldsymbol{\alpha=2.0}$\\$\beta=1.0$} & \thead{$35.71$\\$74$\\$264$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SNL-20_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SNL-20_TRF.png}} \\
\thead{SRNL\\$\boldsymbol{\alpha=1.5}$\\$\beta=1.0$} & \thead{$35.58$\\$84$\\$285$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SNL-15_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SNL-15_TRF.png}} \\
\thead{SRNL\\$\boldsymbol{\alpha=1.0}$\\$\beta=1.0$} & \thead{$35.31$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SNL-10_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SNL-10_TRF.png}} \\
\thead{SRNL\\$\boldsymbol{\alpha=0.5}$\\$\beta=1.0$} & \thead{$34.58$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SNL-05_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SNL-05_TRF.png}} \\
\hline
\thead{SRNL\\$\alpha=2.0$\\$\boldsymbol{\beta=0.4}$} & \thead{$35.69$\\$50$\\$258$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SRNL-20-04_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SRNL-20-04_TRF.png}}\\
\thead{SRNL\\$\alpha=2.0$\\$\boldsymbol{\beta=0.2}$} & \thead{$35.63$\\$26$\\$110$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SRNL-20-02_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SRNL-20-02_TRF.png}} \\
\thead{SRNL\\$\alpha=2.0$\\$\boldsymbol{\beta=0.1}$} & \thead{$35.59$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SRNL-20-01_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SRNL-20-01_TRF.png}} \\
\thead{SRNL\\$\alpha=2.0$\\$\boldsymbol{\beta=0.05}$} & \thead{$35.48$\\$\boldsymbol{\infty}$\\$\boldsymbol{\infty}$} & \thead{\includegraphics[width=3cm,height=1.8cm]{figures/VResNet-feat-SRNL-20-005_sv.png}} & \thead{\vspace{-0.55cm}\\ $t$\vspace{0.25cm}\\ $X$\vspace{0.25cm}\\ $Y$} \hspace{-0.3 cm} \thead{\makebox[\w cm]{\raggedleft $-40$} \makebox[\w cm]{$-30$} \makebox[\w cm]{$-20$} \makebox[\w cm]{$-10$} \makebox[\w cm]{$0$} \makebox[\w cm]{$+10$} \makebox[\w cm]{$+20$} \makebox[\w cm]{$+30$} \makebox[\w cm]{\raggedright $+40$}\\ \includegraphics[width=11cm, height=1.29cm]{figures/VResNet-feat-SRNL-20-005_TRF.png}} \\
\hline
\end{tabular}
\end{table*}

Finally, let us consider the models trained with \mbox{SRNL-2.0-$\beta$} for $\beta \in \{0.4, 0.2, 0.1, 0.05\}$ in lines~6 to 9 of Table~\ref{table:constrained_models}. As expected, varying $\beta$ has no effect on the spectral norm of the convolutional layers, but it has an effect on their stable rank, or the area-under-the-curve of their singular value spectra. Again, our test on the long video sequence and our spatio-temporal receptive field diagnostic show that there is a value of $\beta$ for which the stability of the model changes: models trained with $\beta > 0.1$ are unstable while the models trained with $\beta < 0.1$ are stable.  This observation confirms that our Soft Lipschitz Constraint is also effective at promoting stability. Interestingly, reducing $\beta$ also shortens the temporal length of the receptive field but the effect is softer than with $\alpha$, suggesting that controlling the stable rank of the linear layers of a model has a softer effect on its Lipschitz constant than controlling their spectral norms. Importantly, the cost of stability in terms of performance is now lower, and we obtain a stable model that performs better than with the Hard Lipschitz Constraint approach ($+0.18$dB between $\alpha = 1.0, \beta = 1.0$ and $\alpha = 2.0, \beta = 0.1$).

\subsection{Discussion}

In the previous sections, we showed that inference-time stability can be enforced during training by constraining the Lipschitz constant of the model to be lower than~1. In this section, we discuss possible alternative strategies.

Given a pre-trained model known to be unstable, one could consider ways to operate it in a stable manner. One approach would for instance consist in running the model burst by burst---either without overlap (e.g. running frames 1 to 10, then 11 to 20, then 21 to 30, etc.), with partial overlap (e.g. frames 1-10, 5-15, 10-20, etc.) or with full overlap (e.g. frames 1-10, 2-11, 3-12, etc.)---while resetting the recurrent features to zero between each burst. This strategy would prevent instabilities from building up, but it presents a number of issues. Without overlap, the performance fluctuates, the model constantly having to go through a new burn-in period, starting from its performance on a single frame. With overlap, the approach becomes redundant and computationally inefficient, therefore losing one of the main advantages of using a recurrent model in the first place. Moreover, running the model burst by burst introduces discontinuities which are likely to be visually perceptible in the form of flickering artefacts. Another approach would consist in \emph{dampening the recurrent features} by a factor $\lambda < 1$, allowing a smooth transition between a stable, single frame regime ($\lambda = 0$), and an unstable fully recurrent regime ($\lambda = 1$). This approach is illustrated on a sequence of 700 frames in Figure~\ref{feature_dampening}, and we study it further in Appendix~B, where we confirm that the price of stability in terms of performance is much higher than with our Hard and Soft Lipschitz Constraints (see also the summary Table~\ref{table:summary}).

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.45\textwidth]{figures/feature_dampening.pdf}
\end{center}
\caption{Feature dampening of VResNet-feat for four dampening factors $\lambda$ on a video sequence of 700 frames. Decreasing $\lambda$ improves stability but has a strong negative impact on performance.}
\label{feature_dampening}
\end{figure}

\setlength{\tabcolsep}{5pt}
\begin{table}
\begin{center}
\caption{Summary Table. We compare the performances of VResNet-feat in different scenarios. The soft Lipschitz constraint offers the best performance for a stable model.}
\label{table:summary}
\begin{tabular}{lcc}
\hline
\noalign{\smallskip}
VResNet-feat with \ldots & $\text{PSNR}_7$ & Stable \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
No Constraint & $35.74$ & \xmark\\
Feature Dampening ($\lambda = 0.55$) & $34.62$ & \cmark\\
Hard Lipschitz Constraint (SRNL-1.0-1.0) & $35.31$ & \cmark\\
Soft Lipschitz Constraint (SRNL-2.0-0.1) & $35.59$ & \cmark\\
\hline
\end{tabular}
\end{center}
\end{table}

The instabilities studied in this paper could also be interpreted as a domain adaptation problem: models trained on short sequences fail to generalize to sequences of several hundred frames. To test this hypothesis however, we face computational and data constraints. It is unrealistic to train large recurrent video processing models on sequences of more than 10 to 20 frames---the training process involves backpropagation through time, which has large memory
requirements---and even if it was possible, collecting the required data would quickly become impractical. To work around these issues, we perform experiments on a small VDnCNN model where the number of internal convolutions has been reduced to only one, allowing us to unroll the model up to 56 times through time during training, and we generate long sequences with synthetic motion from single frames. We show in Appendix~C that, not only does the model trained on sequences of 56 frames still suffer from instabilities at inference time, but it also suffers from instabilities at training time due to exploding gradients.

\section{Conclusion}

In this paper, we have identified and characterized a serious vulnerability affecting recurrent networks for video restoration tasks: they can be unstable and fail catastrophically on long video sequences. To avoid problems in practice, we recommend to follow some guidelines. (1) The stability of the model should always be tested, either by evaluating it on hours of video data, or preferably by actively looking for unstable sequences, using our spatio-temporal receptive field diagnostic tool. (2) In safety-critical applications, stability can be guaranteed by applying a Hard Lipschitz Constraint on the spectral norms of the convolutional layers (SRNL with $\alpha < 1$ and $\beta = 1$). (3) In non safety-critical applications, stability can be obtained with minimal performance loss by applying a Soft Lipschitz Constraint on the stable rank of the convolutional layers (SRNL with $\alpha > 1$ and $\beta < 1$).

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}