# “Sparse + Low-Rank” Tensor Completion Approach for Recovering Images and
Videos

Chenjian Pan1 and Chen Ling1 and Hongjin He2 and Liqun Qi3,4 and Yanwei Xu3
Manuscript received October XX, 2021; revised July XX, 2022. Corresponding
author: H. He (email: hehongjin@nbu.edu.cn). 1Department of Mathematics,
School of Science, Hangzhou Dianzi University, Hangzhou, 310018, China.  2
School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China.
3Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co.,
Ltd., Shatin, New Territory, Hong Kong, China.  4Department of Applied
Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong
Kong, China.

###### Abstract

Recovering color images and videos from highly undersampled data is a
fundamental and challenging task in face recognition and computer vision. By
the multi-dimensional nature of color images and videos, in this paper, we
propose a novel tensor completion approach, which is able to efficiently
explore the sparsity of tensor data under the discrete cosine transform (DCT).
Specifically, we introduce two “sparse + low-rank” tensor completion models as
well as two implementable algorithms for finding their solutions. The first
one is a DCT-based sparse plus weighted nuclear norm induced low-rank
minimization model. The second one is a DCT-based sparse plus $p$-shrinking
mapping induced low-rank optimization model. Moreover, we accordingly propose
two implementable augmented Lagrangian-based algorithms for solving the
underlying optimization models. A series of numerical experiments including
color image inpainting and video data recovery demonstrate that our proposed
approach performs better than many existing state-of-the-art tensor completion
methods, especially for the case when the ratio of missing data is high.

###### Index Terms:

Tensor completion, $p$-shrinkage thresholding, weighted nuclear norm, discrete
cosine transform, image inpainting.

##  I Introduction

With the rapid developments of sensor technologies and video surveillance
systems, the collected images and videos are naturally stored as multi-way
arrays, which are also called tensors. As we know, the complete information of
images and videos is very important to make a good decision for intelligent
devices or data users. However, during the acquisition process, observed image
and video data often contain missing entries (or pixels). In this situation,
estimating these missing information of images and videos, which is also
called tensor completion, is a fundamental and challenging problem in the
communities of image processing and computer vision, e.g., see [1, 2, 3, 4]
and references therein.

It is well-known that tensor is a higher-order extension of matrix, so the
tensor completion is also a natural generalization of matrix completion.
Generally speaking, when the missing entries are sparse in an incomplete
matrix, we could efficiently explore the local information around the unknown
components to get a relatively ideal completion to the matrix, e.g., see [5,
6, 7]. However, when dealing with a highly undersampled matrix, it is
incredibly difficult, even if not impossible, to accurately estimate these
missing entries from an incomplete matrix without any global or prior
information. Comparatively, the complex structure of tensors makes that
recovering the missing entries from a highly undersampled tensor puts forward
more theoretical and computational challenges at the interface of statistics
and optimization, e.g., see [8]. In the past decades, it is well-documented
that exploiting the inherent global information, e.g., low-rank and sparsity,
of the data is able to greatly improve the estimation quality of highly
undersampled matrices and tensors, e.g., see [9, 10, 11, 12, 13], to name just
a few.

As a direct extension of the low-rank matrix completion, the canonical low-
rank tensor completion (LRTC) model is expressed mathematically as

$\begin{array}[]{cl}\min\limits_{\mathcal{X}}&{\rm rank}(\mathcal{X})\\\
\text{s.t.}&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}(\mathcal{H}),\end{array}$
(1)

where both $\mathcal{X}$ and $\mathcal{H}$ are $N$-th order tensors, ${\rm
rank}(\cdot)$ denotes the rank function, $\Omega$ is the index set
corresponding to the observed entries of the incomplete tensor $\mathcal{H}$,
and ${\mathscr{P}}_{\Omega}(\cdot)$ is the linear operator that keeps known
elements in $\Omega$ while setting the others to be zeros. It has been
documented in [14, 15] that directly minimizing the rank function of tensors,
even for matrices, is an NP-hard problem. Moreover, unlike the unique
definition of rank for matrices, there are diverse definitions for tensors
such as CANDECOMP/PARAFAC (CP) rank, Tucker rank and Tensor Train (TT) rank
(see [16, 17]). Consequently, the diversity of tensor ranks often makes
engineers difficult to choose an appropriate surrogate for characterizing the
low-rankness of their problems.

Roughly speaking, most state-of-the-art tensor completion methods can be
grouped into two categories. (i) The first type refers to the tensor nuclear
norm minimization approach, which unfolds the underlying tensor as a series of
matrices so that we could efficiently employ the matrix nuclear norm as an
approximation to the rank of a tensor. Therefore, many efficient algorithms
tailored for matrix completion could be naturally extended to tensor
completion based on the so-called tensor nuclear norm definitions, e.g., see
[18, 9, 11, 19, 20, 21, 22, 23] and references therein. Mathematically, a
seminal tensor nuclear norm minimization model introduced in [9] takes the
form

$\begin{array}[]{cl}\min\limits_{\mathcal{X}}&\sum_{n=1}^{N}\alpha_{n}\|X_{(n)}\|_{*}\\\
\text{s.t.}&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}(\mathcal{H}),\end{array}$
(2)

where $\alpha_{n}\geq 0~{}(n\in[N]:=\\{1,2,\cdots,N\\})$ can be regarded as
weight parameters often satisfying $\sum_{n=1}^{N}\alpha_{n}\approx 1$, matrix
$X_{(n)}$ corresponds to the mode-$n$ unfolding of tensor $\mathcal{X}$ for
every $n\in[N]$, and $\|\cdot\|_{*}$ represents the well-known nuclear norm
referring to the sum of all singular values of a matrix. Note that a vector
consisting of the ranks of unfolding matrices $X_{(n)}$’s $(n=1,2,\cdots N)$
is called the Tucker rank of the tensor $\mathcal{X}$ (see [16]). Hence, the
objective function in (2) is indeed a convexly weighted sum of the components
of Tucker rank. Compared with the direct vectorization and matricization
approches for tensor data, model (2) efficiently exploits the multi-mode
structure, thereby possibly achieving a better approximation to the low-
rankness of tensor data. Moreover, these unfolding completion models (i.e.,
tensor nuclear norm minimization models) are beneficial for algorithmic design
due to the convexity of tensor nuclear norm functions. Recently, the state-of-
the-art alternating direction method of multipliers (ADMM) and Douglas-
Rachford splitting method have been successfully applied to tensor completion,
e.g., see [9, 10, 24, 25, 26]. (ii) The second type of tensor completion
approach is based on tensor decomposition. Actually, we observe that many
tensor nuclear norm based models utilize the so-called unfolding (or
matricization) technique. However, Yuan and Zhang [27] showed that the
matricization for higher-order tensors ignores the nature of tensors and
potentially destroys some inherent properties of the data, thereby leading to
suboptimal procedure, which encourages researchers to develop new completion
methods from tensor decomposition perspectives. In the literature, some
popular tensor decomposition techniques include CP decomposition, Tucker
decomposition [16], T-SVD [28] and Tensor-Train decomposition [17]. Like the
matrix decomposition, the aforementioned tensor decomposition forms have also
been verified as powerful dimensionality reduction tools, which can promote
the low-rankness of tensor data to some extent. Empirically, these tensor
decomposition based completion models have received great successes in big
data analysis, pattern recognition, and traffic data recovery, e.g., see [29,
12, 13, 30, 31, 32, 33, 34] and references therein.

When regarding color images and videos as general tensors, the aforementioned
tensor completion approaches are certainly applicable to images and video
inpainting problems. However, it often fails to achieve an ideal restoration
quality for highly undersampled image data since only the low-rank property is
exploited in general tensor completion models (see Figs. 4 and 6). As we know,
the total variation (TV) regularization (see [35]) is a widely used tool in
the community of image processing to preserve sharp discontinuities (edges) of
an image, while removing noise and other unwanted fine scale detail. Hence,
researchers judiciously incorporated TV regularization into low-rank tensor
completion models for the purpose of exploiting the inherent structure of
images. The promising numerical performance can be found in recent works,
e.g., [36, 22, 37, 33, 38, 39, 40]. From the mathematical modeling
perspective, the underlying images usually are sparse under the TV transform.
Consequently, we see that an $\ell_{1}$-norm is used to promote the sparsity
of an image in the TV transform domain, which demonstrates that combining the
low-rank and TV-based sparse prior information simultaneously can greatly
improve the restoration quality. However, as stated in [41], the traditional
TV regularizer is still not perfect, since it only guarantees an estimation
presenting a locally smooth visualization, while ignoring the global
perception and structure. Such a drawback motives us to find new sparse
surrogates to recover more accurate data. Actually, in the image processing
literature, the well-known discrete cosine transform (DCT) has been widely
used for the most popular image compression standard JPEG, since DCT is
powerful to obtain a (at least approximately) sparse representation of an
image. For example, we consider a widely used gray video, i.e., sidewalk (see
Fig. 1), which is a third order tensor of size $220\times 352\times 30$. By
performing DCT on each dimension of such a gray video, a large number of
elements of approach to zeros, thereby leading to a high level sparsity when
setting a truncated number (TN), e.g., $0.05$ and $0.1$, to drop all values
less than such a TN. However, the video recovered directly from the truncated
tensor is still close to the original one, which means that a small sample
information is possible to recover an ideal (at least identifiable) one. Such
an experimental observation also encourages us to consider a sparsity
regularization on the coefficient tensor under the DCT procedure. Here, we
refer the reader to [42, 43, 44, 45, 41, 46, 47] for recent applications of
DCT on image recovery and some completion methods considering the property of
the tensor data in transformed domains, e.g., see [18, 48, 49, 50]. Compared
to the TV-based tensor completion model, to the best of our knowledge, DCT-
based approaches received much less considerable attention on color images and
videos inpainting from tensor completion angle. Hence, we are motivated to
make a further study on showing the ability of the DCT technique for
recovering images and videos from highly undersampled data.

Original TN=0.05 TN=0.1  Original PSNR 35.24 PSNR 31.28

Figure 1: The first row show the visualization of the sparsity of the gray
video sidewalk under DCT, where the white represents $0$. The second row
illustrates the comparisons of the 10-th frame of the original video and the
frames reconstructed from the truncated tensor.

In this paper, we introduce two “sparse + low-rank” tensor completion
approaches for recovering color images and videos. Our contribution is four-
fold.

  * •

Most nuclear norm based tensor completion models equally treat all singular
values of the unfolding matrices. For some real-world data sets, small
singular values are often sensitive to the incomplete (or corrupted by noise)
observed information, thereby possibly leading to a suboptimal low-rank
tensor. In this situation, we will propose a minimization model, whose
objective function is the sum of a DCT-based sparse regularization term and a
weighted nuclear norm induced low-rank regularization term so that the
singular values have different weights to enhance the global low-rank
structure.

  * •

In many unfolding approaches, the most popular low-rank surrogate of tensors
is the nuclear norm of unfolding matrices. Recently, both theoretical and
empirical results show that the so-called $p$-shrinkage thresholding algorithm
outperforms the classical iterative soft thresholding algorithm induced by
nuclear norm for low-rank and sparse recovery problems, e.g., see [51, 52,
53]. Accordingly, the second contribution of this paper is that we introduce a
nonconvex optimization model, which minimizes the sum of a DCT-based sparse
term and a $p$-shrinking mapping induced low-rank term.

  * •

We develop two implementable augmented Lagrangian-based algorithms for the
proposed tensor completion models, where all subproblems of our algorithms
have closed-form solutions.

  * •

We conduct a series of experiments on color images and surveillance videos.
Our computational results demonstrate that our proposed “sparse + low-rank”
tensor completion approaches outperform many state-of-the-art model-driven
tensor completion methods, especially for highly undersampled cases.

The structure of this paper is as follows. In Section II, we summarize some
notations and recall some basic definitions including (weighted) nuclear norm
of matrices, $p$-shrinkage mapping and proximal operators. In Section III, we
will first introduce a unified “sparse + low-rank” tensor completion approach.
Then, we split this section into two parts and propose two kinds of “sparse +
low-rank” tensor completion models, respectively. Based on the augmented
Lagrangian function, we also propose two implementable algorithms for the
underlying tensor completion models. Numerically, in Section IV, we conduct
the performance of our approaches on images and videos recovery from highly
undersampled data. Finally, some concluding remarks are provided in Section V.

##  II Notations and Preliminaries

In this section, we summarize some notations and definitions on $p$-shrinkage
mapping and weighted nuclear norm that will be used throughout this paper.

Tensor is a multidimensional array, which is an extension of matrix. The space
of all $N$-th order real tensors is denoted by $\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N}}$, where the order of a tensor is also called
way or mode. Given an $N$-th order $\mathcal{A}\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N}}$, we denote the $(i_{1},i_{2},\ldots,i_{N})$-th
component of $\mathcal{A}$ by $a_{i_{1}i_{2}\ldots i_{N}}$. So the $N$-th
order tensor $\mathcal{A}$ is also denoted by
$\mathcal{A}=(a_{i_{1}i_{2}\ldots i_{N}})$. Throughout this paper, tensors of
order $N\geq 3$ are denoted by calligraphical letters, e.g.,
$\mathcal{A},\mathcal{B},\ldots$. Generally, we use capital letters (e.g.,
$A,B,\ldots$), boldfaced lowercase letters (e.g., ${\bm{a}},{\bm{b}},\ldots$),
and lowercase letters (e.g., $a,b,\ldots$) to denote matrices, vectors, and
scalars, respectively. For any two $N$-th order real tensors
$\mathcal{A}=(a_{i_{1}i_{2}\ldots i_{N}})$ and
$\mathcal{B}=(b_{i_{1}i_{2}\ldots i_{N}})$, the inner product between
$\mathcal{A}$ and $\mathcal{B}$ is given by

$\langle\mathcal{A},\mathcal{B}\rangle:=\sum_{i_{1},i_{2},\ldots,i_{N}}a_{i_{1}i_{2}\ldots
i_{N}}b_{i_{1}i_{2}\ldots i_{N}}.$

Consequently, the Frobenius norm of tensor $\mathcal{A}$ associated with the
above inner product is given by
$\|\mathcal{A}\|_{F}=\sqrt{\langle\mathcal{A},\mathcal{A}\rangle}$. Given an
$N$-th order tensor $\mathcal{A}$, the mode-$n$ matricization (or unfolding)
of $\mathcal{A}$ is denoted by $A_{(n)}$, and the
$(i_{1},i_{2},\ldots,i_{N})$-th entry of tensor $\mathcal{A}$ is mapped to the
$(i_{n},j)$-th entry of matrix $A_{(n)}$ in the lexicographical order, where

$j=1+\sum_{1\leq l\leq N,l\neq n}(i_{l}-1)J_{l}~{}~{}~{}~{}{\rm
with}~{}~{}~{}\displaystyle J_{l}=\prod_{1\leq t\leq l-1,t\neq n}I_{t}.$

Given a matrix $A\in\mathbb{R}^{m\times n}$, we write its singular value
decomposition (SVD) as $A=U\Lambda V^{\top}$, where $U$ and $V$ are orthogonal
matrices and $\Lambda$ is a diagonal matrix, i.e.,

$\Lambda={\rm diag}(\sigma(A))={\rm
diag}\left(\sigma_{1}(A),\sigma_{2}(A),\cdots,\sigma_{r}(A)\right)$

with $r:=\min\\{m,n\\}$, and the diagonals $\sigma_{i}(A)$’s are singular
values of $A$ satisfying
$\sigma_{1}(A)\geq\sigma_{2}(A)\geq\cdots\geq\sigma_{r}(A)$ without loss of
generality. With the above preparation, we first recall the definition of
(weighted) nuclear norm of a matrix (see [43]).

######  Definition 2.1.

For any given matrix $A\in\mathbb{R}^{m\times n}$, its nuclear norm is defined
by

$\|A\|_{*}=\sum_{i=1}^{r}\sigma_{i}(A)$

and the weighted nuclear norm is given by

$\|A\|_{*,{\bm{w}}}=\sum_{i=1}^{r}{w}_{i}\sigma_{i}(A)$

where $r:=\min\\{m,n\\}$ and $\sigma_{i}(A)$ is the $i$-th largest singular
value of $A$, and ${\bm{w}}=(w_{1},\cdots,w_{r})$ is a weight vector, which,
as suggested in [19], is given by

${w}_{i}=\delta/(\sigma_{i}(A)+\epsilon),\quad i=1,2,\cdots,r,$

where $\delta\in\mathbb{R}_{+}$ is a constant and $\epsilon$ is a small
positive number to avoid division by $0$. In algorithmic implementation, we
can iteratively update ${w}_{i}$’s.

Below, we recall the $p$-shrinkage mapping introduced in [52].

######  Definition 2.2.

Given ${\bm{a}}\in\mathbb{R}^{n}$, $\mu>0$ and $p\leq 1$, the $p$-shrinkage
thresholding operator is defined in component-wise by

${\rm\bf
pshrink}({\bm{a}},\mu,p)=\text{sign}({\bm{a}})\odot\max\left\\{|{\bm{a}}|-\mu|{\bm{a}}|^{p-1},\;0\right\\},$
(3)

where ‘${\rm sign}(\cdot)$’ and ‘$|\cdot|$’ are the sign function and absolute
value function in component-wise, respectively, and ‘$\odot$’ represents the
component-wise product between two vectors. In particular, when setting $p=1$,
the $p$-shrinkage operator (3) immediately reduces to the well-known soft-
thresholding, which is denoted by

${\rm
shrink}({\bm{a}},\mu)=\text{sign}({\bm{a}})\odot\max\left\\{|{\bm{a}}|-\mu,\;0\right\\}.$
(4)

Clearly, the smaller $p$ is, the less ${\rm shrink}({\bm{a}},\mu,p)$ shrinks
large inputs. We refer the reader to [53] for an illustration to the
philosophy of the $p$-shrinkage operator.

For any given ${\bm{a}}\in\mathbb{R}^{n}$, the proximal operator associated
with $\theta:\mathbb{R}^{n}\to\mathbb{R}$ about $\tau>0$ is defiend as

$\text{prox}_{\theta,\tau}({\bm{a}}):=\arg\min_{{\bm{x}}\in\mathbb{R}^{n}}\left\\{\theta({\bm{x}})+\frac{\tau}{2}\|{\bm{x}}-{\bm{a}}\|^{2}\right\\}.$

Consequently, as shown in [54, Theorem 4] (see also [55]), for any $\mu>0$,
$A\in{\mathbb{R}}^{m\times n}$ and a weight vector ${\bm{w}}$, the global
optimal solution to the following optimization problem

$\min_{X}\|X\|_{*,{\bm{w}}}+\frac{1}{2\mu}\|X-A\|^{2}_{F}$

is given by the weighted SVD thresholding

$X^{*}=U{\rm\bf wshrink}(\Lambda,\mu,{\bm{w}})V^{\top},$

where $A=U\Lambda V^{\top}$ is the SVD of $A$ and

${\rm\bf
wshrink}(\Lambda,\mu,{\bm{w}})=\max\left\\{\sigma(A)-\mu{\bm{w}},\;0\right\\}.$
(5)

Moreover, it follows from [51] that the $p$-shrinkage mapping defined in
Definition 2.2 can also be interpreted as the proximal operator of a penalty
function $\Phi_{p}^{\mu}(\cdot):\mathbb{R}^{n}\to\mathbb{R}$, i.e.,

${\rm\bf
pshrink}({\bm{a}},\mu,p)=\arg\min_{{\bm{x}}\in\mathbb{R}^{n}}\left\\{\Phi_{p}^{\mu}({\bm{x}})+\frac{1}{2\mu}\|{\bm{x}}-{\bm{a}}\|^{2}\right\\},$

where $\Phi_{p}^{\mu}({\bm{x}}):=\sum_{i=1}^{n}\phi_{p}^{\mu}(x_{i})$ with
$\phi_{p}^{\mu}(x_{i})$ being even, concave, nondecreasing and continuous on
$[0,\infty]$, differentiable on $(0,\infty)$, nondifferentiable at 0 with the
subdifferential being $\partial\phi_{p}^{\mu}(0)=[-1,1]$. We refer the reader
to [51, Theorem 1] (also [56, 53]) for more details. Notice that the
$p$-shrinkage operator is available to matrix variables. Specifically, for the
optimization problem

$\min_{X}\Phi_{p}^{\mu}(X)+\frac{1}{2\mu}\|X-A\|^{2}_{F},$ (6)

we have its globally optimal solution given by

$X^{*}=U{\rm\bf pshrink}(\Lambda,\mu,p)V^{\top},$ (7)

where $A=U\Lambda V^{\top}$ is the SVD of $A$ and

${\rm\bf pshrink}(\Lambda,\mu,p)={\rm\bf pshrink}(\sigma(A),\mu,p).$

##  III Models and Algorithm

In this section, we aim to develop DCT-based sparse plus nonconvex functions
induced low-rank tensor completion approaches to images and videos recovery.
Mathematically, we first introduce a unified “sparse + low-rank” tensor
completion model for $N$-th order tensors as follows:

$\begin{array}[]{cl}\min\limits_{\mathcal{X}}&{\rm
rank}(\mathcal{X})+\lambda\|\mathcal{{\mathscr{D}}(X)}\|_{0}\\\
\text{s.t.}&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}({\mathcal{H}}),\end{array}$
(8)

where ${\mathscr{D}}(\cdot)$ denotes the multi-dimensional DCT operator
satisfying orthogonality, $\|\cdot\|_{0}$ represents the so-called
$\ell_{0}$-norm to characterize the sparsity of DCT’s coefficients, and
$\lambda>0$ is a tuning parameter. Due to the appearances of rank function and
$\ell_{0}$ norm, the optimization model (8) is a highly non-convex and NP-hard
problem. Usually, we can find an approximate solution of (8) by employing the
(non-) convex relaxations of rank function and $\ell_{0}$-norm, respectively.
Therefore, in this section, we first introduce a DCT-based sparse plus
weighted nuclear norm (WNN) induced low-rank tensor completion model. Then, we
propose a DCT-based sparse plus $p$-shrinking mapping induced low-rank tensor
completion model. Additionally, we will propose two implementable augmented
Lagrangian-based splitting methods to solve the underlying models.

###  III-A DCT-based sparse + WNN induced low-rank minimization model

As shown in the literature, directly minimizing the sum of the rank function
and $\ell_{0}$-norm of tensor $\mathcal{X}$ in (8) is not an easy task. So,
how to approximate the rank of tensors is crucial for improving the completion
quality. In this subsection, we use the sum of the weighted nuclear norms of
the unfolding matrices to approximate the rank of $\mathcal{X}$ and employ the
$\ell_{1}$-norm to replace the $\ell_{0}$-norm for promoting the sparsity of
images under the DCT. Accordingly, we call the model DCT-based sparse + WNN
induced low-rank minimization model, which is expressed as the form

$\begin{array}[]{cl}\displaystyle\min_{\mathcal{X}}&\displaystyle\sum_{i=1}^{N}\alpha_{i}\|X_{(i)}\|_{*,{\bm{w}}}+\lambda\|\mathcal{{\mathscr{D}}(X)}\|_{1}\\\
\text{s.t.}&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}({\mathcal{H}}).\end{array}$
(9)

Apparently, two parts of the objective function in model (9) are nonsmooth,
but both have promising structures so that their proximal operators enjoy
explicit forms. To exploit the structure of model (9), we here first introduce
auxiliary variables to separate the two nonsmooth terms in the objective
function, thereby leading to a separable optimization model, i.e.,

$\begin{array}[]{cl}\displaystyle\min_{\mathcal{X}}&\sum_{i=1}^{N}\alpha_{i}\|Y_{i,(i)}\|_{*,{\bm{w}}}+\lambda\|\mathcal{T}\|_{1}\\\
\text{s.t.}&\mathcal{X}=\mathcal{Y}_{i},\quad\text{for all}~{}i\in[N],\\\
&\mathcal{T}={\mathscr{D}}({\mathcal{X}}),\\\
&{\mathscr{P}}_{\Omega}({\mathcal{X}})={\mathscr{P}}_{\Omega}({\mathcal{H}}).\end{array}$
(10)

where $Y_{i,(i)}$ represents the mode-$i$ unfolding of tensor
$\mathcal{Y}_{i}$ for $i\in[N]$. Clearly, model (10) is an equality-
constrained optimization problem, then its augmented Lagrangian function reads
as

$\displaystyle{\bm{L}}(\mathcal{Y}_{i},{\mathcal{X}},\mathcal{T},\mathcal{S}_{i},\mathcal{Q})$
$\displaystyle:=\sum_{i=1}^{N}\left(\alpha_{i}\|Y_{i,(i)}\|_{*,{\bm{w}}}+\left\langle\mathcal{S}_{i},{\mathcal{X}}-\mathcal{Y}_{i}\right\rangle+\frac{\beta}{2}\|{\mathcal{X}}-\mathcal{Y}_{i}\|_{F}^{2}\right)$
$\displaystyle\quad+\lambda\|\mathcal{T}\|_{1}+\left\langle\mathcal{Q},\mathcal{T}-{\mathscr{D}}({\mathcal{X}})\right\rangle+\frac{\beta}{2}\|\mathcal{T}-{\mathscr{D}}({\mathcal{X}})\|_{F}^{2},$
(11)

where $\mathcal{S}_{i}$ and $\mathcal{Q}$ are Lagrangian multipliers
associated to $X_{(i)}=Y_{i,(i)}$ and
$\mathcal{T}={\mathscr{D}}({\mathcal{X}})$, respectively, and $\beta$ are
positive penalty parameters. By (III-A), we follow the alternating spirit of
ADMM to design an implementable algorithm. Theoretically, all primal variables
can be updated in any order due to their equal roles. However, their updating
order is slightly sensitive to the numerical performance. Notice that the
weight of the low-rank term is usually greater than the sparse part, we
empirically first update $\mathcal{Y}_{i}$ and then calculate $\mathcal{X}$
due to newly introduced equality constraint. Thirdly, we update $\mathcal{T}$
for the reason that we can immediately utilize the latest information of
$\mathcal{X}$. Finally, we update the Lagrangian multipliers $\mathcal{S}_{i}$
and $\mathcal{Q}$ simultaneously. Therefore, we accordingly update the
variables in (III-A) via the order
$\mathcal{Y}_{i}\to\mathcal{X}\to\mathcal{T}\to\mathcal{S}_{i}\to\mathcal{Q}$.
Specifically, for given
$(\mathcal{X}^{k},\mathcal{T}^{k},\mathcal{S}_{i}^{k},\mathcal{Q}^{k})$, we
update the $(k+1)$-th iterates via the following process:

  * •

The update of $\mathcal{Y}_{i}$ ($i\in[N]$) reads as

$\displaystyle\mathcal{Y}^{k+1}_{i}$
$\displaystyle=\arg\min_{\mathcal{Y}_{i}}{\bm{L}}\left({\mathcal{Y}_{i},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)$
$\displaystyle=\arg\min_{\mathcal{Y}_{i}}\left\\{\alpha_{i}\|Y_{i,(i)}\|_{*,{\bm{w}}}+\frac{\beta_{k}}{2}\left\|\mathcal{Y}_{i}-\widehat{\mathcal{Y}}_{i}^{k}\right\|_{F}^{2}\right\\}$
$\displaystyle={\rm{fold}}\left(U_{k}{\rm\bf
wshrink}\left(\Lambda^{k},\;\frac{\alpha_{i}}{\beta_{k}},\;{\bm{w}}_{i}\right)V_{k}^{\top}\right),$
(12)

where ‘fold($\cdot$)’ corresponds to the inverse operator of mode-$i$
unfolding, ‘${\rm\bf wshrink}(\cdot,\cdot,\cdot)$’ is given by (5) and

$\widehat{\mathcal{Y}}_{i}^{k}={\mathcal{X}}^{k}+\frac{1}{\beta_{k}}{\mathcal{S}}_{i}^{k}\quad\text{and}\quad\widehat{Y}_{i,(i)}^{k}=U_{k}\Lambda^{k}V_{k}^{\top}.$

  * •

With the latest $\mathcal{Y}^{k+1}_{i}$, we obtain $\mathcal{X}^{k+1}$ via
solving

$\min_{\mathcal{X}}\left\\{{\bm{L}}\left({\mathcal{Y}^{k+1}_{i},{\mathcal{X}},\mathcal{T}^{k},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)\;|\;{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}(\mathcal{H})\right\\},$

which can be expressed explicitly by

$\left\\{\begin{array}[]{l}\mathcal{X}^{k+1}_{\Omega}=\mathcal{H}_{\Omega},\\\
{\mathcal{X}}^{k+1}_{\Omega^{c}}=\frac{1}{N+1}\widehat{\mathcal{X}}^{k}_{\Omega^{c}},\end{array}\right.$
(13)

where $\Omega^{c}$ denotes the complementary set of $\Omega$ and

$\widehat{\mathcal{X}}^{k}=\sum_{i=1}^{N}\left(\mathcal{Y}_{i}^{k+1}-\frac{1}{\beta_{k}}\mathcal{S}_{i}^{k}\right)+{\mathscr{D}}^{-1}\left(\mathcal{T}^{k}+\frac{1}{\beta_{k}}\mathcal{Q}^{k}\right).$

  * •

For the $\mathcal{T}$-subproblem, we have

$\displaystyle\mathcal{T}^{k+1}$
$\displaystyle=\arg\min_{\mathcal{T}}{\bm{L}}\left({\mathcal{Y}^{k+1}_{i},{\mathcal{X}}^{k+1},\mathcal{T},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)$
$\displaystyle=\arg\min_{\mathcal{T}}\left\\{\lambda\|\mathcal{T}\|_{1}+\frac{\beta_{k}}{2}\left\|\mathcal{T}-\widehat{{\mathcal{T}}}^{k}\right\|_{F}^{2}\right\\}$
$\displaystyle=\text{shrink}\left(\widehat{{\mathcal{T}}}^{k},\frac{\lambda}{\beta_{k}}\right),$
(14)

where ‘shrink($\cdot,\cdot$)’ is given by (4) and

$\widehat{{\mathcal{T}}}^{k}={\mathscr{D}}({\mathcal{X}}^{k+1})-\frac{1}{\beta_{k}}\mathcal{Q}^{k}.$

  * •

With the above latest
$(\mathcal{Y}_{i}^{k+1},\mathcal{X}^{k+1},\mathcal{T}^{k+1})$, we update the
two Lagrangian multipliers $\mathcal{S}^{k+1}_{i}$ and $\mathcal{Q}^{k+1}$ via

$\mathcal{S}^{k+1}_{i}=\mathcal{S}^{k}_{i}+\beta_{k}\left({\mathcal{X}}^{k+1}-\mathcal{Y}^{k+1}_{i}\right)$
(15)

and

$\mathcal{Q}^{k+1}=\mathcal{Q}^{k}+\beta_{k}\left(\mathcal{T}^{k+1}-{\mathscr{D}}({\mathcal{X}}^{k+1})\right),$
(16)

respectively.

With the above preparations, we formally summarize the updating schemes for
model (10) in Algorithm 1.

Algorithm 1 ADMM for Model (10)

Input: Initial starting points
${\mathcal{X}}^{0},\mathcal{Y}^{0},\mathcal{T}^{0},\mathcal{S}_{0},\mathcal{Q}_{0}$
and $\beta_{0}>0$.
1: Update $\mathcal{Y}_{i}^{k+1}$ simultaneously via (• ‣ III-A) for $i=[N]$;
2: Update ${\mathcal{X}}^{k+1}$ via (13);
3: Update $\mathcal{T}^{k+1}$ via (• ‣ III-A);
4: Update $\mathcal{S}_{i}^{k+1}$ simultaneously via (15) for $i=[N]$;
5: Update $\mathcal{Q}^{k+1}$ via (16);
6: Update $\beta_{k+1}=\varrho\beta_{k}$ with $\varrho>1$;
7: Until a termination criterion is fulfilled.
Output: ${\mathcal{X}}^{*}$.

###  III-B DCT-based sparse + $p$-shrinking mapping induced low-rank
optimization model

In model (9), we employ the sum of the weighted nuclear norms of the unfolding
matrices $X_{(i)}$ to approximate the low-rankness of the data. However, we do
not know whether such an approximation is enough ideal for color images and
videos tensor data. Recently, the so-called $p$-shrinking algorithm is widely
used in low-rank and sparse recovery problems. Hence, in this subsection, we
further consider the combination of $p$-shrinking low-rank penalty and DCT-
driven sparse regularization, and propose the following tensor completion
model:

$\begin{array}[]{cl}\min\limits_{\mathcal{X}}&\sum_{i=1}^{N}\alpha_{i}\Phi_{p}^{u}(X_{(i)})+\lambda\|\mathcal{{\mathscr{D}}(X)}\|_{1}\\\
\text{s.t.}&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}({\mathcal{H}}),\end{array}$
(17)

where $p\leq 1$ and $\Phi_{p}^{u}(\cdot)$ is a nonconvex penalty function
defined in (6). Compared to model (9), the only difference is that we here
employ the $\Phi_{p}^{u}(X_{(i)})$ to replace the weighted nuclear norm term
$\|X_{(i)}\|_{*,\bm{w}}$. So, both (9) and (17) share the same structure
except the low-rank-inducing term. For simplicity, we use the symbols in (10)
again, then model (17) can be rewritten as the following separable
optimization problem, i.e.,

$\begin{array}[]{cl}\min\limits_{\mathcal{X}}&\sum_{i=1}^{N}\alpha_{i}\Phi_{p}^{u}(Y_{i,(i)})+\lambda\|\mathcal{T}\|_{1}\\\
\text{s.t.}&\mathcal{X}=\mathcal{Y}_{i},\quad\text{for all }~{}i\in[N],\\\
&\mathcal{T}={\mathscr{D}}(\mathcal{X}),\\\
&{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}({\mathcal{H}}).\end{array}$
(18)

Correspondingly, the augmented Lagrangian function for (18) reads as

$\displaystyle{\bm{L}}(\mathcal{Y}_{i},{\mathcal{X}},\mathcal{T},\mathcal{S}_{i},\mathcal{Q})$
$\displaystyle:=\sum_{i=1}^{N}\left(\alpha_{i}\Phi_{p}^{\mu}(Y_{i,(i)})+\left\langle\mathcal{S}_{i},{\mathcal{X}}-\mathcal{Y}_{i}\right\rangle+\frac{\beta}{2}\|{\mathcal{X}}-\mathcal{Y}_{i}\|_{F}^{2}\right)$
$\displaystyle\quad+\lambda\|\mathcal{T}\|_{1}+\left\langle\mathcal{Q},\mathcal{T}-{\mathscr{D}}({\mathcal{X}})\right\rangle+\frac{\beta}{2}\|\mathcal{T}-{\mathscr{D}}({\mathcal{X}})\|_{F}^{2}.$
(19)

Based upon (III-B), by invoking the update idea of Algorithm 1, i.e.,
$\mathcal{Y}_{i}\to\mathcal{X}\to\mathcal{T}\to\mathcal{S}_{i}\to\mathcal{Q}$,
we derive the detailed iterative schemes for solving model (18).

  * •

Update $\mathcal{Y}_{i}^{k+1}$ via

$\displaystyle\mathcal{Y}^{k+1}_{i}$
$\displaystyle=\arg\min_{\mathcal{Y}_{i}}{\bm{L}}\left({\mathcal{Y}_{i},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)$
$\displaystyle=\arg\min_{\mathcal{Y}_{i}}\left\\{\alpha_{i}\Phi_{p}^{\mu}(Y_{i,(i)})+\frac{\beta_{k}}{2}\left\|\mathcal{Y}_{i}-\widehat{\mathcal{Y}}_{i}^{k}\right\|_{F}^{2}\right\\}$
$\displaystyle={\rm{fold}}\left(\tilde{U}_{k}{\rm\bf
pshrink}\left(\tilde{\Lambda}^{k},\;\frac{\alpha_{i}}{\beta_{k}},\;p\right)\tilde{V}_{k}^{\top}\right),$
(20)

where ‘${\rm\bf pshrink}(\cdot,\cdot,\cdot)$’ is given by (3) and

$\widehat{\mathcal{Y}}_{i}^{k}={\mathcal{X}}^{k}+\frac{1}{\beta_{k}}\mathcal{S}_{i}^{k}\quad\text{and}\quad\widehat{Y}_{i,(i)}^{k}=\tilde{U}_{k}\tilde{\Lambda}^{k}\tilde{V}_{k}^{\top}.$

  * •

We obtain $\mathcal{X}^{k+1}$ via solving

$\min_{\mathcal{X}}\left\\{{\bm{L}}\left({\mathcal{Y}^{k+1}_{i},{\mathcal{X}},\mathcal{T}^{k},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)\;|\;{\mathscr{P}}_{\Omega}(\mathcal{X})={\mathscr{P}}_{\Omega}(\mathcal{H})\right\\},$

which can also be expressed explicitly by

$\left\\{\begin{array}[]{l}\mathcal{X}^{k+1}_{\Omega}=\mathcal{H}_{\Omega},\\\
{\mathcal{X}}^{k+1}_{\Omega^{c}}=\frac{1}{N+1}\widehat{\mathcal{X}}^{k}_{\Omega^{c}}\end{array}\right.$
(21)

where

$\widehat{\mathcal{X}}^{k}=\sum_{i=1}^{N}\left(\mathcal{Y}_{i}^{k+1}-\frac{1}{\beta_{k}}\mathcal{S}_{i}^{k}\right)+{\mathscr{D}}^{-1}\left(\mathcal{T}^{k}+\frac{1}{\beta_{k}}\mathcal{Q}^{k}\right).$

  * •

Update $\mathcal{T}^{k+1}$ via

$\displaystyle\mathcal{T}^{k+1}$
$\displaystyle=\arg\min_{\mathcal{T}}{\bm{L}}\left({\mathcal{Y}^{k+1}_{i},{\mathcal{X}}^{k+1},\mathcal{T},\mathcal{S}^{k}_{i},\mathcal{Q}^{k}}\right)$
$\displaystyle=\text{shrink}\left({\mathscr{D}}({\mathcal{X}}^{k+1})-\frac{1}{\beta_{k}}\mathcal{Q}^{k},\frac{\lambda}{\beta_{k}}\right).$
(22)

  * •

Finally, update the two Lagrangian multipliers $\mathcal{S}_{i}^{k+1}$ and
$\mathcal{Q}^{k+1}$ via (15) and (16), respectively.

Formally, we summarize the iterative schemes for (18) in Algorithm 2.

Algorithm 2 ADMM for Model (18).

Input: Initial starting points
${\mathcal{X}}^{0},\mathcal{Y}^{0},\mathcal{T}^{0},\mathcal{S}_{0},\mathcal{Q}_{0}$.
1: Update $\mathcal{Y}_{i}^{k+1}$ simultaneously via (• ‣ III-B) for $i=[N]$;
2: Update ${\mathcal{X}}^{k+1}$ via (21);
3: Update $\mathcal{T}^{k+1}$ via (• ‣ III-B);
4: Update $\mathcal{S}_{i}^{k+1}$ simultaneously via (15) for $i=[N]$;
5: Update $\mathcal{Q}^{k+1}$ via (16);
6: Update $\beta_{k+1}=\varrho\beta_{k},\varrho>1$;
7: Until a termination criterion is fulfilled.
Output: ${\mathcal{X}}^{*}$.

###  III-C Convergence results

In this subsection, we follow the way used in [57] to prove the convergence
result of Algorithm 1 for problem (10) under some assumptions. Since Algorithm
2 share the almost same iterative schemes expect the $\mathcal{Y}$-subproblem,
we skip the convergence analysis of Algorithm 2 for model (18) for the
conciseness of the paper.

######  Lemma 3.1.

Suppose that both
$\\{S^{k}\\}:=\\{\mathcal{S}_{1}^{k},\dots,\mathcal{S}_{N}^{k}\\}$ and
$\\{\mathcal{Q}^{k}\\}$ are bounded, the sequences
$\\{\mathcal{Y}^{k}\\}:=\\{\mathcal{Y}_{1}^{k},\cdots,\mathcal{Y}^{k}_{N}\\}$
and $\\{\mathcal{T}^{k}\\}$ produced by Algorithm 1 are bounded.

###### Proof.

From the definition of
${\bm{L}}(\mathcal{Y},{\mathcal{X}},\mathcal{T},\mathcal{S},\mathcal{Q})$, we
have

$\displaystyle{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k},\mathcal{Q}^{k})-{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k-1},\mathcal{Q}^{k-1})$
$\displaystyle=\sum_{i=1}^{N}\left\langle\mathcal{S}_{i}^{k}-\mathcal{S}_{i}^{k-1},{\mathcal{X}}^{k}-\mathcal{Y}_{i}^{k}\right\rangle+\langle\mathcal{Q}^{k}-\mathcal{Q}^{k-1},\mathcal{T}^{k}-\mathscr{D}({\mathcal{X}}^{k})\rangle$
$\displaystyle~{}~{}~{}+\frac{\beta_{k}-\beta_{k-1}}{2}\left(\sum_{i=1}^{N}\|{\mathcal{X}}^{k}-\mathcal{Y}_{i}^{k}\|_{F}^{2}+\|\mathcal{T}^{k}-\mathscr{D}({\mathcal{X}}^{k})\|_{F}^{2}\right)$
$\displaystyle=\frac{1}{\beta_{k-1}}\left(\sum_{i=1}^{N}\|\mathcal{S}_{i}^{k}-\mathcal{S}_{i}^{k-1}\|_{F}^{2}+\|\mathcal{Q}^{k}-\mathcal{Q}^{k-1}\|_{F}^{2}\right)$
$\displaystyle~{}~{}~{}+\frac{\beta_{k}-\beta_{k-1}}{2\beta_{k-1}^{2}}\left(\sum_{i=1}^{N}\|\mathcal{S}_{i}^{k}-\mathcal{S}_{i}^{k-1}\|_{F}+\|\mathcal{Q}^{k}-\mathcal{Q}^{k-1}\|_{F}^{2}\right)$
$\displaystyle=\frac{\beta_{k}+\beta_{k-1}}{2\beta_{k-1}^{2}}\left(\sum_{i=1}^{N}\|\mathcal{S}_{i}^{k}-\mathcal{S}_{i}^{k-1}\|_{F}^{2}+\|\mathcal{Q}^{k}-\mathcal{Q}^{k-1}\|_{F}^{2}\right),$
(23)

where the second equality follows from (15) and (16). Then, it follows from
the iterative schemes of Algorithm 1 and (III-C) that

$\displaystyle{\bm{L}}(\mathcal{Y}^{k+1},{\mathcal{X}}^{k+1},\mathcal{T}^{k+1},\mathcal{S}^{k},\mathcal{Q}^{k})$
$\displaystyle\leq{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k},\mathcal{Q}^{k})$
$\displaystyle={\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k-1},\mathcal{Q}^{k-1})$
$\displaystyle~{}~{}~{}+\frac{\beta_{k}+\beta_{k-1}}{2\beta_{k-1}^{2}}\left(\sum_{i=1}^{N}\|\mathcal{S}_{i}^{k}-\mathcal{S}_{i}^{k-1}\|_{F}^{2}+\|\mathcal{Q}^{k}-\mathcal{Q}^{k-1}\|_{F}^{2}\right).$
(24)

By invoking $\beta_{k}=\varrho\beta_{k-1}$ with $\varrho>1$, we immediately
prove
$\sum_{i=1}^{\infty}\frac{\beta_{k}+\beta_{k-1}}{2\beta_{k-1}^{2}}<\infty$. As
a consequence of (III-C), the sequence
$\\{{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k},\mathcal{Q}^{k})\\}$
is upper-bounded due to the boundedness of $\\{\mathcal{S}^{k}\\}$ and
$\\{Q^{k}\\}$. Rearranging terms of
$\\{{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k},\mathcal{Q}^{k})\\}$
immediately yields

$\displaystyle\sum_{i=1}^{N}\left(\alpha_{i}\|Y^{k}_{i,(i)}\|_{*,\bm{w}}\right)+\lambda\|\mathcal{T}^{k}\|_{1}$
$\displaystyle={\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k-1},\mathcal{Q}^{k-1})-\frac{\beta_{k-1}^{-1}}{2}\left(\|\mathcal{Q}^{k}\|_{F}^{2}-\|\mathcal{Q}^{k-1}\|_{F}^{2}\right)$
$\displaystyle~{}~{}~{}-\frac{\beta_{k-1}^{-1}}{2}\sum_{i=1}^{N}\left(\|\mathcal{S}_{i}^{k}\|_{F}^{2}-\|\mathcal{S}_{i}^{k-1}\|_{F}^{2}\right),$

which, together with the boundedness of the sequences
$\\{{\bm{L}}(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k-1},\mathcal{Q}^{k-1})\\}$,
$\\{\mathcal{S}^{k}\\}$ and $\\{\mathcal{Q}^{k}\\}$, implies that
$\\{Y^{k}_{i,(i)}\\}$ and $\\{\mathcal{T}^{k}\\}$ for all $i\in[N]$ are
bounded, since $\|\cdot\|_{*,\bm{w}}$ and $\|\cdot\|_{1}$ are nonnegative. ∎

######  Theorem 3.2.

Let
$\left\\{\left(\mathcal{Y}^{k},{\mathcal{X}}^{k},\mathcal{T}^{k},\mathcal{S}^{k},\mathcal{Q}^{k}\right)\right\\}$
be a sequence generated by Algorithm 1. Suppose that both
$\\{\mathcal{S}^{k}\\}$ and $\\{\mathcal{Q}^{k}\\}$ are bounded, and further
satisfy
$\lim\limits_{k\rightarrow\infty}\|\mathcal{S}^{k+1}-\mathcal{S}^{k}\|_{F}=0$
and
$\lim\limits_{k\rightarrow\infty}\|\mathcal{Q}^{k+1}-\mathcal{Q}^{k}\|_{F}=0$,
respectively. Then,

  * (i).

$\\{{\mathcal{X}}^{k}\\},\\{\mathcal{Y}^{k}\\},\\{\mathcal{T}^{k}\\}$ are
bounded Cauchy sequences.

  * (ii).

any accumulation point
$\left\\{\left(\mathcal{Y}^{\infty},{\mathcal{X}}^{\infty},\mathcal{T}^{\infty},\mathcal{S}^{\infty},\mathcal{Q}^{\infty}\right)\right\\}$
satisfies the KKT condition of model (10).

###### Proof.

For any $i\in[N]$, it easily follows from the iterative scheme (15) and
$\lim\limits_{k\rightarrow\infty}\beta_{k}=\infty$ that the sequence
$\\{{\mathcal{X}}^{k}\\}$ is bounded due to Lemma 3.1. Moreover, by the
properties of $\\{\mathcal{S}^{k}\\}$ and $\\{\mathcal{Q}^{k}\\}$, we have

$\left\\{\begin{array}[]{l}\lim_{k\rightarrow\infty}\|{\mathcal{X}}^{k+1}-\mathcal{Y}_{i}^{k+1}\|_{F}=0,\\\
\lim_{k\rightarrow\infty}\|\mathcal{T}^{k+1}-\mathscr{D}({\mathcal{X}}^{k+1})\|_{F}=0,\end{array}\right.$
(25)

which further implies that $\\{\mathcal{Y}^{k}\\}$ and $\\{\mathcal{T}^{k}\\}$
approach to feasible solutions.

Now, we show that $\\{{\mathcal{X}}^{k}\\}$, $\\{\mathcal{Y}^{k}\\}$,
$\\{\mathcal{T}^{k}\\}$ are Cauchy sequences. Here, we only show
$\\{\mathcal{Y}^{k}\\}$ being a Cauchy sequence, while the other sequences can
be proved in a similar way.

Invoking the first-order optimality condition of the $\mathcal{Y}$-subproblm
yields

$\displaystyle 0$
$\displaystyle\in\alpha_{i}\partial_{C}\|Y_{i,(i)}^{k+1}\|_{*,\bm{w}}-\beta_{k}\left(X_{(i)}^{k}-Y_{i,(i)}^{k+1}+\frac{1}{\beta_{k}}S_{i,(i)}^{k}\right),$

which, together with (15), leads to

$\displaystyle
X_{(i)}^{k}-X_{(i)}^{k+1}\in\frac{\alpha_{i}\partial_{C}\|Y_{i,(i)}^{k+1}\|_{*,\bm{w}}-S_{i,(i)}^{k+1}}{\beta_{k}}.$
(26)

By the boundeness of both $\\{Y_{i,(i)}^{k}\\}$ and
$\\{\mathcal{S}_{i}^{k}\\}$ and properties of $\|\cdot\|_{*,\bm{w}}$, it
follows from (26) that $\|X_{(i)}^{k}-X_{(i)}^{k+1}\|_{F}=O(\beta_{k}^{-1})$,
which together with
$\sum_{i=0}^{\infty}\beta_{k}^{-1}=\frac{\varrho}{\beta_{0}(\varrho-1)}<\infty$,
implies that $\\{{\mathcal{X}}^{k}\\}$ is a Cauchy sequence, and it
immediately has a limit point.

Let ${\mathcal{X}}^{\infty}$, $\mathcal{Y}^{\infty}$, $\mathcal{T}^{\infty}$,
$\mathcal{S}^{\infty}$, $\mathcal{Q}^{\infty}$ be the limit points of
$\\{{\mathcal{X}}^{k}\\}$, $\\{\mathcal{Y}^{k}\\}$, $\\{\mathcal{T}^{k}\\}$,
$\\{\mathcal{S}^{k}\\}$, $\\{\mathcal{Q}^{k}\\}$, respectively. It first
follows from (25) that

${\mathcal{X}}^{\infty}=\mathcal{Y}_{i}^{\infty},(i=1,\ldots,N)\;\;\text{and}\;\;\mathcal{T}^{\infty}=\mathscr{D}({\mathcal{X}}^{\infty}).$

Rearranging (26) arrives at

$\displaystyle 0$
$\displaystyle\in\alpha_{i}\partial_{C}\|Y_{i,(i)}^{k+1}\|_{*,\bm{w}}-S_{i,(i)}^{k+1}-\beta_{k}\left(X_{(i)}^{k}-X_{(i)}^{k+1}\right)$
$\displaystyle=\alpha_{i}\partial_{C}\|\mathcal{Y}_{i}^{k+1}\|_{*,\bm{w}}-\mathcal{S}_{i}^{k+1}-\beta_{k}\left({\mathcal{X}}^{k}-{\mathcal{X}}^{k+1}\right).$
(27)

Consequently, taking limit on (III-C) immediately yields
$\mathcal{S}_{i}^{\infty}\in\alpha_{i}\partial_{C}\|\mathcal{Y}_{i}^{\infty}\|_{*,\bm{w}}$.

By the first-order optimality condition of the ${\mathcal{X}}$-subproblem, we
have $\bar{X}$

$\left\\{\begin{array}[]{l}\sum\limits_{i=1}^{N}\left(\mathcal{S}_{i}^{k}+\beta_{k}({\mathcal{X}}^{k+1}-\mathcal{Y}_{i}^{k+1})\right)\\\
\qquad+\beta_{k}\left({\mathcal{X}}^{k+1}-\mathscr{D}^{-1}(\mathcal{T}^{k})\right)-\mathscr{D}^{-1}(\mathcal{Q}^{k})=0,\\\
{\mathscr{P}}_{\Omega}(\mathcal{X}^{k+1})={\mathscr{P}}_{\Omega}({\mathcal{H}}),\end{array}\right.$

Taking $k\to\infty$ on the above two equalities leads to

$\sum\limits_{i=1}^{N}\mathcal{S}_{i}^{\infty}=\mathscr{D}^{-1}(\mathcal{Q}^{\infty})\;\text{
and
}\;{\mathscr{P}}_{\Omega}(\mathcal{X}^{\infty})={\mathscr{P}}_{\Omega}({\mathcal{H}}).$

Finally, the first-order optimality condition of the $\mathcal{T}$-subproblem
reads as

$\displaystyle 0$
$\displaystyle\in\partial\lambda\|\mathcal{T}^{k+1}\|_{1}+\beta_{k}\left(\mathcal{T}^{k+1}-\mathscr{D}(X^{k+1})+\beta_{k}^{-1}\mathcal{Q}^{k}\right)$
$\displaystyle=\partial\lambda\|\mathcal{T}^{k+1}\|_{1}+\mathcal{Q}^{k}+\beta_{k}\left(\mathcal{T}^{k+1}-\mathscr{D}({\mathcal{X}}^{k+1})\right)$
$\displaystyle=\partial\lambda\|\mathcal{T}^{k+1}\|_{1}+\mathcal{Q}^{k+1}.$

Consequently, we have
$-\mathcal{Q}^{*}\in\partial\lambda\|\mathcal{T}^{*}\|_{1}$ when
$k\rightarrow\infty$. Therefore, we conclude that the accumulation point
satisfies the KKT condition of model (10). ∎

Hereafter, we only give the time complexity analysis of Algorithm 1 and omit
the analysis of Algorithm 2 since both of them share the almost iterative
scheme and the same SVD.

The main time cost of Algorithm 1 is consuming by performing SVD and multi-
dimensional DCT. In each iteration, the complexity of subproblem
$\mathcal{Y}^{k+1}_{i}~{}(i\in[N])$ is
$O\left(\sum_{i=1}^{N}(I_{i})^{2}\times\Pi_{j\neq i}I_{j}\right)$. The
complexities of subproblem ${\mathcal{X}}^{k+1}$ and $\mathcal{T}^{k+1}$ are
both $O\left(\Pi_{i=1}^{N}I_{i}\times\log\Pi_{i=1}^{N}I_{i}\right)$. In
addition, the complexities to update $\mathcal{S}_{i}^{k+1}~{}(i\in[N])$ and
$\mathcal{Q}^{k+1}$ are $O(N\Pi_{i=1}^{N}I_{i})$ and $O(\Pi_{i=1}^{N}I_{i})$.
So, the time complexity of each iteration is
$O\left(\sum_{i=1}^{N}(I_{i})^{2}\times\Pi_{j\neq
i}I_{j}+\Pi_{i=1}^{N}I_{i}\times\log\Pi_{i=1}^{N}I_{i}\right)$ Thus, the total
time complexity of Algorithm 1 is
$O\left(t\left(\sum_{i=1}^{N}(I_{i})^{2}\times\Pi_{j\neq
i}I_{j}+\Pi_{i=1}^{N}I_{i}\times\log\Pi_{i=1}^{N}I_{i}\right)\right)$, where
$t$ is the number of iterations.

##  IV Numerical Experiments

In this section, we are concerned with the numerical performance of our
approach proposed in Section III on images and videos recovery. Here, we will
consider two kinds of images and videos data sets: 1) RGB images; 2)
surveillance videos. All algorithms were implemented in MATLAB R2018b (64bit)
and experiments were conducted on a laptop computer with Intel(R) Core(TM)
i7-7500 CPU @2.70GHz and 8GB memory. Throughout this section, we denote
Algorithms 1 and 2 by ‘DCT-WNN’ and ‘DCT-IpST’ for simplicity, respectively.
Moreover, we also compare the proposed algorithms with eight state-of-the-art
tensor completion approaches as follows:

  * •

IpST[53]: Iterative $p$-shrinkage thresholding algorithm for solving low
Tucker rank tensor recovery problem, which only employs a nonconvex penalty
function $\Phi_{p}^{\mu}(\cdot)$ given in (6) to replace the traditional
nuclear norm of unfolding matrices.

  * •

TTNNL1[44]: Using the truncated tensor nuclear norm for low-rank
approximation, and a sparse regularization term combined with the 3-D DCT
bases.

  * •

F-TNN[48]111https://github.com/TaiXiangJiang/Framelet-TNN: Framelet
representation of tensor nuclear norm for third-order tensor completion.

  * •

TNN-3DTV[39]: Anisotropic total variation regularized low-rank tensor
completion based on tensor nuclear norm, which utilizes the 3D total variation
regularization to exploit the structure of images.

  * •

TCTF[12]222https://panzhous.github.io/: Tensor factorization for low-rank
tensor completion, which uses the operation of T-product to decompose a tensor
into two smaller tensors.

  * •

WSTNN[58]333https://yubangzheng.github.io/ybz/: Tensor N-tubal rank and its
convex relaxation for low-rank tensor recovery, which defines the weighted sum
of the tensor nuclear norm.

  * •

SMF-LRTC[59]444https://github.com/zhaoxile/Low-rank-tensor-completion-via-
smooth-matrix-factorization: Low-rank tensor completion via smooth matrix
factorization, which exploits the piecewise smoothness prior of tensors by
introducing smoothness constraints on the factor matrices. Here, we only use
it for video experiments, because such a model is designed for video and
hyperspectral image data sets.

  * •

DP3LRTC[50]: Using tensor nuclear norm to characterize the global low-rankness
prior and plugging a denoising neural network, which learned from a large
number of natural images. It is a deep learning method.

For the fair comparison, we take

$\text{RelCha}=\frac{\|{\mathcal{X}}^{k+1}-{\mathcal{X}}^{k}\|_{F}}{\|{\mathcal{X}}_{\rm{true}}\|_{F}}\leq
10^{-4},$ (28)

as the stopping criterion for all methods, where ${\mathcal{X}}_{\rm{true}}$
is the true tensor. Moreover, the following metrics are chosen to evaluate the
recovery performance of the different algorithms.

  * •

Peak Signal-to-Noise Ratio (PSNR [12]) is defined as:

$\text{PSNR}=10\log_{10}\frac{(\\#\mathcal{X}_{\rm
true})\cdot({\mathcal{X}}_{\rm
true}^{\max})^{2}}{\|{\mathcal{X}}^{*}-{\mathcal{X}}_{\rm true}\|_{F}^{2}}$

to measure the quality of the restored tensor data by an algorithm, where
$(\\#\mathcal{X}_{\rm true})$ denotes the number of elements of
$\mathcal{X}_{\rm true}$, ${\mathcal{X}}_{\rm true}^{\max}$ represents the
largest element of ${\mathcal{X}}_{\rm true}$, and ${\mathcal{X}}^{*}$
corresponds to the restored tensor.

  * •

Structural Similarity (SSIM [60])555Matlab package:
https://ece.uwaterloo.ca/$\sim$z70wang/research/ssim/. is defined as:

${\rm
SSIM}=\displaystyle\frac{(2\mu_{X}\mu_{X^{*}}+a_{1})(2\sigma_{XX^{*}}+a_{2})}{(\mu_{X}^{2}+\mu^{2}_{X^{*}}+a_{1})(\sigma_{X}^{2}+\sigma^{2}_{X^{*}}+a_{2})},$

where $X$ and $X^{*}$ denote the greyscale images for the original image and
its recovered image, respectively; $a_{1}$ and $a_{2}$ are constants;
$\mu_{X}$ and $\mu_{X^{*}}$ denote the average values, while $\sigma_{X}$ and
$\sigma_{X^{*}}$ denote the standard deviation of $X$ and $X^{*}$,
respectively; and $\sigma_{XX^{*}}$ denote the covariance matrix between $X$
and $X^{*}$.

Since there are some parameters in models and algorithms, for both models (10)
and (18), we set $(\alpha_{1},\alpha_{2},\alpha_{3})=(1/3,1/3,10^{-3})$ for
image inpainting and $(\alpha_{1},\alpha_{2},\alpha_{3})=(1/3,1/3,1/3)$ for
video inpainting, respectively. Moreover, we take $\lambda=0.05$ and
$\lambda=10^{-2}$ for (10) and (18), respectively. For the algorithmic
parameters, we set $p=0.2$ for DCT-IpST throughout the experiments. In
addition, we set $\varrho=1.2$ and $\beta^{0}=10^{-5}$, respectively. All
parameters of the other compared algorithms were taken as the default values
used in the paper.

###  IV-A RGB image inpainting

In this subsection, we consider the RGB image inpainting problem, where RGB
images namely include Red, Green, and Blue channels and the number of channels
corresponds to the modes of a third order tensor. Here, we conduct the
numerical performance our approach on $16$ widely used
images666http://r0k.us/graphics/kodak/, which are summarized in Fig. 2. Here,
the eight images in the first two rows of Fig. 2 are $256\times 256\times 3$,
and the remaining eight images are $512\times 768\times 3$ except image woman
of size $768\times 512\times 3$. These images have no visual features such as
low-rank and sparsity. However, as shown in Fig. 3, the sparse structure is
apparent when applying DCT to these images, which also sufficiently supports
that the main idea of this paper is reasonable.

airplane baboon facade house
peppers sailboat giant butterfly
caps woman motorbikes buildings
valley girl aircraft window

Figure 2: The sixteen RGB images for experiments.
Figure 3: Sparsity level of sixteen RGB images under DCT, where “sparsity
level” is defined as the proportion of the number of zero elements in a
tensor.

Now, we are concerned with the inpainting performance of our approach on the
cases where the pixels of images are missed in a random way. In Fig. 4, we
first consider four scenarios on the sampling rate (‘sr’), i.e., ${\sf
sr}=\\{3\%,5\%,10\%,20\%\\}$, for five images. Clearly, except the deep
learning method DP3LRTC, the recovered images by our methods, i.e., DCT-WNN
and DCT-IpST, are better than the other compared model-driven methods for the
scenarios where sr’s are lower than $10\%$ (see the first four columns of Fig.
4). To investigate the full sensitivity of these methods to sr, we further
consider five scenarios on sr’s from $3\%$ to $30\%$ for the images listed in
Fig. 2, and plot PSNR values with respect to sr’s in Fig. 5. It can be easily
seen from Fig. 5 that both DCT-WNN and DCT-IpST outperform the other compared
methods except the deep learning method DP3LRTC in terms of taking higher PSNR
values for all scenarios with ${\sf sr}\leq 20\%$.

caps girl window aircraft motorbikes

Figure 4: Images recovered by the nine algorithms for the cases with random
missing information. The top row corresponds to the observed incomplete
images. From left to right: downsampled images with ${\sf
sr}=3\%,3\%,5\%,10\%$ and $20\%$, respectively. From the second row to bottom:
Images recovered by IpST, TTNNL1, F-TNN, TNN-3DTV, TCTF, WSTNN, DP3LRTC, DCT-
IpST and DCT-WNN, respectively.

Figure 5: PSNR values with respect to different sampling rates for the sixteen
RGB images in Fig. 2.

Below, we are interested in the numerical performance on structurally missing
scenarios such as missing slices or shape/text mask (i.e., downsampling
operator). Specifically, we consider five scenarios as shown by the first row
of Fig. 6. Obviously, we see from the last two rows in Fig. 6 that our DCT-WNN
and DCT-IpST have promising ability to recover the structurally missing
images. Moreover, from the PSNR, SSIM, and computing time in seconds (TIME(s)
for short) reported in Table I, we can see that the proposed DCT-WNN and DCT-
IpST have better numerical performance than the compared methods except the
deep learning method DP3LRTC. However, our DCT-WNN and DCT-IpST take less
computing time than DP3LRTC to achieve comparable PSNR and SSIM values when
all methods ran on a general personal computer without GPU acceleration. Those
results efficiently demonstrate that the popular deep learning methods usually
obtain better inpainting quality than the traditional model-driven approaches.
However, model-driven approaches are still necessary for real-world
applications due to their relatively low requirements on computer hardware.

caps-1 caps-2 girl-1 girl-2 motorbikes

Figure 6: Images recovered by the nine algorithms for the cases with
structurally missing information. From the second row to bottom: Images
recovered by IpST, TTNNL1, F-TNN, TNN-3DTV, TCTF, WSTNN, DP3LRTC, DCT-IpST and
DCT-WNN, respectively. TABLE I: Numerical results of the nine algorithms for
recovering images with structurally missing pixels as tested in Fig. 6.

| Method | caps-1 |  | caps-2 |  | girl-1 |  | girl-2 |  | motorbikes
---|---|---|---|---|---|---|---|---|---|---
PSNR | SSIM | TIME |  | PSNR | SSIM | TIME |  | PSNR | SSIM | TIME |  | PSNR | SSIM | TIME |  | PSNR | SSIM | TIME
| IpST | 17.28 | 0.558 | 53.81 |  | 17.87 | 0.749 | 52.21 |  | 25.01 | 0.892 | 55.29 |  | 23.24 | 0.668 | 62.14 |  | 16.01 | 0.902 | 29.03
| TTNNL | 24.07 | 0.711 | 55.37 |  | 26.86 | 0.857 | 55.31 |  | 31.22 | 0.942 | 53.25 |  | 23.70 | 0.724 | 56.93 |  | 21.62 | 0.967 | 46.87
| F-TNN | 17.00 | 0.540 | 135.08 |  | 17.87 | 0.749 | 25.13 |  | 27.61 | 0.916 | 97.64 |  | 19.11 | 0.559 | 137.30 |  | 9.80 | 0.861 | 34.80
| TNN-3DTV | 18.96 | 0.602 | 315.42 |  | 20.47 | 0.800 | 300.23 |  | 29.38 | 0.934 | 361.91 |  | 22.47 | 0.712 | 323.01 |  | 31.96 | 0.990 | 322.12
| TCTF | 12.70 | 0.130 | 26.43 |  | 18.22 | 0.753 | 30.23 |  | 25.59 | 0.863 | 28.62 |  | 10.94 | 0.135 | 29.64 |  | 16.29 | 0.742 | 25.92
| WSTNN | 19.27 | 0.639 | 167.36 |  | 34.41 | 0.965 | 154.31 |  | 29.05 | 0.081 | 157.83 |  | 16.34 | 0.576 | 168.18 |  | 10.74 | 0.884 | 165.36
| DP3LRTC | 29.04 | 0.933 | 190.79 |  | 39.25 | 0.922 | 218.53 |  | 33.93 | 0.899 | 188.16 |  | 27.30 | 0.890 | 183.15 |  | 35.90 | 0.987 | 182.67
| DCT-IpST | 28.08 | 0.842 | 102.59 |  | 35.84 | 0.973 | 100.13 |  | 31.79 | 0.946 | 99.67 |  | 26.10 | 0.821 | 101.77 |  | 32.90 | 0.991 | 100.06
| DCT-WNN | 28.15 | 0.831 | 116.81 |  | 36.09 | 0.974 | 102.33 |  | 31.76 | 0.943 | 100.07 |  | 26.22 | 0.807 | 114.25 |  | 23.85 | 0.975 | 101.55

###  IV-B Video recovery

The above color images are actually low-dimensional third-order tensors. In
this subsection, we consider higher dimensional cases, i.e., surveillance
video data sets, which are natural third-order and fourth-order tensors
corresponding to grayscale and color videos, respectively. Here, we choose six
grayscale videos including ‘airport’,
‘sidewalk777https://gr.xjtu.edu.cn/web/dymeng/3; the data can also be
downloaded from: http://perception.i2r.a-star.edu.sg/bk_model/bk_index.html.’,
‘lunges’, ‘biking’, ‘baby888http://crcv.ucf.edu/data/UCF101.php’ and
‘basketball999https://github.com/csyongdu/’ for experiments. Here, we add a
‘camera-shake’ operation to ‘airport’ and ‘sidewalk’ so that their backgrounds
are not static. Typical frames in these videos are depicted in Fig. 7.

We also first check the sparsity level of videos data sets when applying DCT
to videos. The results in Fig. 8 clearly demonstrate that videos also appear
sparse structure under DCT, since the six video data sets have more than
$60\%$ zeros, which means that DCT is an ideal technique for promoting
sparsity of video data sets.

airport

sidewalk lunges biking baby basketball

Figure 7: Some frames of six videos under test. Figure 8: Sparsity level of
video data sets under DCT.

Now, we turn our attention to investigating the performance of our approach on
incomplete videos data. In our experiments, we conduct four scenarios on the
sampling rate, i.e., ${\sf sr}=\\{5\%,10\%,20\%,30\%\\}$, for the six video
data sets. The PSNR, SSIM and TIME(s) values of the six videos obtained by the
algorithms are summarized in Table II, which shows that both DCT-IpST and DCT-
WNN perform better than the other compared methods except the deep learning
method DP3LRTC for the low sampling rate cases (i.e., ${\sf sr}\leq 20\%$).
Here, it is noteworthy that the deep learning method DP3LRTC does not
necessarily always achieve the best results. For example, our approach either
DCT-WNN or DCT-IpST works better than DP3LRTC for “basketball” and “lunges” in
some cases. More interestingly, our DCT-WNN and DCT-IpST always take much less
computing time than DP3LRTC for video data sets to achieve comparable
inpainting quality. In Fig. 9, we first display the destroyed (downsampled)
frames (ten consecutive frames) are listed in the first row, and the recovered
frames by different algorithms are displayed from the second row to the
bottom. From the inpainted frames, it is obvious that both DCT-WNN and DCT-
IpST can successfully obtain relatively ideal videos even for highly
undersampled cases.

TABLE II: Numerical results of the ten algorithms for recovering video data
sets.

Videos Datasets | Method | ${\sf sr}=0.05$ |  | ${\sf sr}=0.10$ |  | ${\sf sr}=0.20$ |  | ${\sf sr}=0.30$
---|---|---|---|---|---|---|---|---
PSNR | SSIM | TIME(s) |  | PSNR | SSIM | TIME(s) |  | PSNR | SSIM | TIME(s) |  | PSNR | SSIM | TIME(s)
| IpST | 17.62 | 0.371 | 16.68 |  | 19.6 | 0.485 | 14.01 |  | 22.23 | 0.661 | 12.41 |  | 24.32 | 0.778 | 10.64
airport | TTNNL1 | 17.98 | 0.499 | 19.81 |  | 20.06 | 0.499 | 19.14 |  | 22.74 | 0.672 | 18.42 |  | 24.68 | 0.777 | 18.48
$144\times 176\times 30$ | F-TNN | 17.94 | 0.372 | 111.83 |  | 20.68 | 0.581 | 113.82 |  | 23.20 | 0.733 | 124.34 |  | 25.12 | 0.826 | 126.64
| TNN-3DTV | 17.44 | 0.297 | 169.11 |  | 19.15 | 0.426 | 136.12 |  | 21.47 | 0.593 | 124.34 |  | 23.46 | 0.713 | 120.98
| TCTF | 6.22 | 0.009 | 15.01 |  | 6.74 | 0.015 | 36.89 |  | 8.00 | 0.030 | 38.51 |  | 11.51 | 0.091 | 39.14
| WSTNN | 18.78 | 0.4403 | 35.34 |  | 20.28 | 0.533 | 27.91 |  | 22.29 | 0.669 | 19.64 |  | 23.99 | 0.761 | 16.71
| SMF-LRTC | 14.73 | 0.161 | 154.23 |  | 19.08 | 0.3967 | 183.62 |  | 23.25 | 0.685 | 196.20 |  | 24.93 | 0.763 | 210.60
| DP3LRTC | 21.14 | 0.629 | 394.33 |  | 23.15 | 0.749 | 384.42 |  | 25.68 | 0.846 | 371.67 |  | 27.82 | 0.911 | 364.87
| DCT-IpST | 18.79 | 0.416 | 33.25 |  | 20.75 | 0.520 | 34.04 |  | 22.98 | 0.660 | 35.40 |  | 24.65 | 0.749 | 34.59
| DCT-WNN | 19.30 | 0.445 | 27.41 |  | 21.31 | 0.559 | 31.09 |  | 23.38 | 0.687 | 27.67 |  | 24.98 | 0.763 | 25.53
| IpST | 19.71 | 0.537 | 64.84 |  | 23.30 | 0.684 | 62.70 |  | 27.22 | 0.823 | 50.37 |  | 29.79 | 0.888 | 44.22
sidewalk | TTNNL1 | 20.40 | 0.557 | 72.28 |  | 23.67 | 0.696 | 72.47 |  | 27.48 | 0.826 | 72.57 |  | 29.80 | 0.881 | 72.46
$220\times 352\times 30$ | F-TNN | 20.12 | 0.551 | 478.43 |  | 21.47 | 0.581 | 475.44 |  | 24.08 | 0.721 | 467.23 |  | 26.27 | 0.800 | 462.11
| TNN-3DTV | 19.35 | 0.463 | 567.70 |  | 21.17 | 0.567 | 462.03 |  | 23.76 | 0.691 | 307.24 |  | 26.00 | 0.781 | 253.84
| TCTF | 6.22 | 0.013 | 121.53 |  | 9.36 | 0.019 | 121.11 |  | 13.39 | 0.114 | 129.77 |  | 18.58 | 0.410 | 121.26
| WSTNN | 23.30 | 0.730 | 100.96 |  | 25.72 | 0.813 | 81.01 |  | 28.38 | 0.880 | 62.80 |  | 30.32 | 0.915 | 48.75
| SMF-LRTC | 18.38 | 0.382 | 506.63 |  | 23.68 | 0.642 | 546.37 |  | 27.91 | 0.810 | 622.66 |  | 29.96 | 0.865 | 631.38
| DP3LRTC | 23.83 | 0.749 | 1230.33 |  | 27.37 | 0.840 | 1273.42 |  | 30.57 | 0.906 | 1272.67 |  | 32.81 | 0.937 | 1215.87
| DCT-IpST | 21.39 | 0.594 | 133.86 |  | 24.41 | 0.711 | 127.81 |  | 27.75 | 0.817 | 122.64 |  | 29.85 | 0.869 | 122.87
| DCT-WNN | 22.04 | 0.624 | 106.72 |  | 25.14 | 0.740 | 105.36 |  | 28.31 | 0.833 | 109.45 |  | 30.29 | 0.880 | 110.15
| IpST | 15.16 | 0.324 | 29.98 |  | 17.08 | 0.451 | 27.26 |  | 19.81 | 0.632 | 23.11 |  | 21.90 | 0.751 | 19.97
basketball | TTNNL1 | 15.95 | 0.405 | 31.87 |  | 18.32 | 0.570 | 28.33 |  | 21.21 | 0.704 | 27.76 |  | 23.37 | 0.808 | 28.21
$144\times 256\times 30$ | F-TNN | 17.33 | 0.465 | 178.08 |  | 19.09 | 0.568 | 182.02 |  | 21.81 | 0.723 | 183.40 |  | 23.93 | 0.819 | 189.24
| TNN-3DTV | 16.12 | 0.351 | 290.96 |  | 17.86 | 0.494 | 217.19 |  | 20.08 | 0.593 | 141.59 |  | 21.95 | 0.749 | 116.23
| TCTF | 5.87 | 0.015 | 26.65 |  | 6.56 | 0.029 | 36.89 |  | 8.34 | 0.083 | 58.17 |  | 12.97 | 0.294 | 59.13
| WSTNN | 16.49 | 0.430 | 45.76 |  | 19.02 | 0.566 | 46.02 |  | 21.29 | 0.702 | 28.76 |  | 23.31 | 0.797 | 23.99
| SMF-LRTC | 14.36 | 0.216 | 221.59 |  | 17.75 | 0.403 | 251.97 |  | 20.88 | 0.609 | 284.98 |  | 22.73 | 0.717 | 306.55
| DP3LRTC | 17.14 | 0.561 | 743.33 |  | 19.17 | 0.688 | 987.42 |  | 22.01 | 0.817 | 984.67 |  | 24.26 | 0.887 | 986.87
| DCT-IpST | 16.89 | 0.421 | 52.67 |  | 20.75 | 0.559 | 53.45 |  | 22.10 | 0.708 | 53.15 |  | 24.03 | 0.786 | 56.45
| DCT-WNN | 17.24 | 0.438 | 41.45 |  | 19.29 | 0.578 | 43.28 |  | 22.42 | 0.717 | 44.86 |  | 24.32 | 0.790 | 46.26
| IpST | 21.30 | 0.663 | 95.15 |  | 25.38 | 0.812 | 78.97 |  | 31.15 | 0.932 | 67.64 |  | 35.50 | 0.970 | 57.82
lunges | TTNNL1 | 21.41 | 0.678 | 70.51 |  | 25.88 | 0.837 | 68.60 |  | 31.67 | 0.942 | 64.75 |  | 35.42 | 0.971 | 64.12
$240\times 320\times 30$ | F-TNN | 23.33 | 0.809 | 448.61 |  | 25.60 | 0.867 | 456.51 |  | 28.91 | 0.922 | 460.82 |  | 31.70 | 0.950 | 462.13
| TNN-3DTV | 22.70 | 0.777 | 784.30 |  | 25.41 | 0.864 | 565.78 |  | 29.04 | 0.926 | 386.18 |  | 32.19 | 0.957 | 310.20
| TCTF | 6.37 | 0.011 | 58.18 |  | 7.45 | 0.021 | 58.39 |  | 12.54 | 0.245 | 59.79 |  | 20.92 | 0.511 | 60.19
| WSTNN | 19.96 | 0.676 | 103.24 |  | 23.77 | 0.808 | 78.69 |  | 27.82 | 0.669 | 68.75 |  | 31.25 | 0.903 | 83.01
| SMF-LRTC | 17.40 | 0.327 | 461.25 |  | 22.98 | 0.675 | 532.40 |  | 29.69 | 0.902 | 601.66 |  | 33.10 | 0.944 | 638.61
| DP3LRTC | 24.55 | 0.873 | 1226.33 |  | 28.14 | 0.933 | 1340.42 |  | 32.71 | 0.971 | 1378.67 |  | 35.94 | 0.984 | 1347.87
| DCT-IpST | 23.43 | 0.774 | 121.29 |  | 27.94 | 0.799 | 125.86 |  | 33.06 | 0.955 | 124.13 |  | 36.36 | 0.976 | 121.36
| DCT-WNN | 24.25 | 0.799 | 105.47 |  | 29.19 | 0.911 | 110.56 |  | 34.18 | 0.963 | 115.50 |  | 37.29 | 0.979 | 118.03
| IpST | 19.54 | 0.588 | 78.98 |  | 23.25 | 0.714 | 70.72 |  | 29.26 | 0.886 | 63.287 |  | 33.17 | 0.945 | 53.48
biking | TTNNL1 | 20.57 | 0.631 | 70.81 |  | 24.16 | 0.750 | 68.96 |  | 29.16 | 0.885 | 66.37 |  | 32.25 | 0.933 | 67.24
$240\times 320\times 30$ | F-TNN | 20.81 | 0.640 | 455.86 |  | 22.83 | 0.701 | 457.11 |  | 26.15 | 0.809 | 463.97 |  | 28.77 | 0.878 | 464.76
| TNN-3DTV | 19.06 | 0.529 | 741.98 |  | 22.08 | 0.659 | 575.65 |  | 25.88 | 0.804 | 412.79 |  | 28.89 | 0.884 | 324.97
| TCTF | 7.44 | 0.011 | 15.01 |  | 8.23 | 0.016 | 36.89 |  | 12.86 | 0.181 | 38.51 |  | 17.18 | 0.500 | 39.14
| WSTNN | 20.49 | 0.660 | 106.80 |  | 24.13 | 0.781 | 80.386 |  | 27.85 | 0.873 | 68.03 |  | 30.76 | 0.921 | 72.38
| SMF-LRTC | 17.21 | 0.417 | 459.85 |  | 23.46 | 0.683 | 530.40 |  | 30.03 | 0.884 | 594.52 |  | 33.29 | 0.932 | 615.38
| DP3LRTC | 25.17 | 0.829 | 1219.33 |  | 28.45 | 0.898 | 1217.42 |  | 31.80 | 0.946 | 1222.67 |  | 34.17 | 0.966 | 1211.87
| DCT-IpST | 21.79 | 0.665 | 121.81 |  | 25.13 | 0.771 | 125.62 |  | 29.62 | 0.884 | 123.93 |  | 32.46 | 0.930 | 125.49
| DCT-WNN | 22.44 | 0.693 | 104.37 |  | 26.17 | 0.810 | 108.59 |  | 30.55 | 0.905 | 115.97 |  | 33.23 | 0.942 | 115.84
| IpST | 20.46 | 0.478 | 81.32 |  | 23.40 | 0.635 | 64.18 |  | 27.30 | 0.810 | 54.44 |  | 30.27 | 0.895 | 45.72
baby | TTNNL1 | 20.64 | 0.499 | 80.29 |  | 23.67 | 0.658 | 70.88 |  | 27.43 | 0.826 | 65.43 |  | 30.16 | 0.887 | 67.48
$240\times 320\times 30$ | F-TNN | 21.32 | 0.542 | 503.42 |  | 23.13 | 0.631 | 454.69 |  | 25.96 | 0.757 | 463.50 |  | 28.16 | 0.835 | 462.16
| TNN-3DTV | 20.50 | 0.467 | 758.46 |  | 22.83 | 0.610 | 463.90 |  | 25.90 | 0.758 | 336.95 |  | 28.35 | 0.845 | 266.91
| TCTF | 8.19 | 0.011 | 51.14 |  | 9.29 | 0.020 | 59.54 |  | 13.23 | 0.179 | 60.43 |  | 19.95 | 0.477 | 60.94
| WSTNN | 21.48 | 0.577 | 100.42 |  | 23.66 | 0.695 | 80.13 |  | 26.42 | 0.811 | 61.08 |  | 28.73 | 0.879 | 50.98
| SMF-LRTC | 18.46 | 0.347 | 489.33 |  | 23.68 | 0.601 | 540.42 |  | 28.28 | 0.810 | 596.67 |  | 30.51 | 0.873 | 625.87
| DP3LRTC | 24.60 | 0.723 | 1208.33 |  | 27.52 | 0.822 | 1213.42 |  | 31.05 | 0.909 | 1216.67 |  | 33.44 | 0.944 | 1237.87
| DCT-IpST | 21.88 | 0.551 | 121.29 |  | 24.71 | 0.689 | 123.93 |  | 27.92 | 0.813 | 124.60 |  | 30.39 | 0.881 | 125.18
| DCT-WNN | 22.63 | 0.592 | 102.43 |  | 25.49 | 0.729 | 105.54 |  | 28.68 | 0.839 | 112.11 |  | 31.13 | 0.898 | 112.27

Figure 9: Visualizations of recovered ‘sidewalk’ data sets by the ten
algorithms. From left to right: ten consecutive observed frames with $20\%$
information. From top to bottom: observed frames, and frames recovered by
IpST, TTNNL1, F-TNN, TNN-3DTV, TCTF, WSTNN, SMF-LRTC, DP3LRTC, DCT-IpST and
DCT-WNN, respectively.

###  IV-C Discussion

Parameters sensitivity: Notice that there are some model parameters in our
models, which are very important for the numerical performance of the models.
However, it is well-known that setting model parameters is an incredibly
difficult task in practice. Generally speaking, we can take constants
empirically according to existing experiments in the literature. Here, we will
conduct the numerical sensitivity of our models’ parameters. Note that there
is a triple of parameters in model (9), i.e.,
$\\{(\alpha_{1},\cdots,\alpha_{N}),\delta,\lambda\\}$. According to [53, 58],
we can easily determine the choice of $\alpha_{i}$’s. So, we below are
concerned with the sensitivity of $\delta$ and $\lambda$. Similarly, for model
(17), we focus on the sensitivity of $p$ and $\lambda$. In our experiments, we
consider the “airport” video data set with ${\sf sr}=30\%$. The parameter
sensitivity results are summarized in Fig. 10. It can be easily seen from Fig.
10 that both models run relatively robust for $\lambda\in[0.01,1]$, which also
provides us some suggestions on the settings for the above experiments.

Figure 10: Numerical sensitivity of model parameters $\lambda$, $\delta$, and
$p$. The left figure corresponds to our first model (9). The right one
corresponds to the second model (17).

Model discussion: Notice that the objective functions of our models consists
of two nonsmooth parts. Ones will be interested in what will happen if we
remove one of the nonsmooth parts. To answer this question, we shall
investigate the numerical performance of our models when removing the low-rank
regularization term or the sparse term. Here, we also focus on the “airport”
video data set with ${\sf sr}=\\{5\%,10\%,20\%,30\%\\}$ in our experiments. In
Fig. 11, “only low-rank term” and “only sparse term” correspond to our models
without sparse term and without low-rank regularization, respectively. From
the plots in Fig. 11, we observe that our models equipped with only one low-
rank term works better than the cases with only one sparse term. However, the
proposed models with sparse and low-rank terms have the best numerical
performance, which also sufficiently supports the idea of this paper.

Figure 11: Numerical performance of our models with only one low-rank
objective or with only one sparse regularization term, respectively.

In summary, the above computational results show that the proposed DCT-WNN and
DCT-IpST are powerful to complete different types of downsampled images and
videos data sets. Although our DCT-WNN and DCT-IpST cannot obtain the same
inpainting quality of the state-of-the-art deep learning method DP3LRTC, DCT-
WNN and DCT-IpST run much faster for large-scale data sets than DP3LRTC on a
general personal computer. From the computing time and computer hardware
perspectives, those model-driven approaches still have their own advantages.
Moreover, we believe that our models could be further improved if some deep
learning techniques are embedded in. We leave it as one of our future
concerns.

##  V Conclusion

In this paper, we introduced a unified “sparse + low-rank” tensor completion
approach, which includes two structured optimization models for recovering
images and videos from highly undersampled data. By introducing auxiliary
variables, we gainfully separated the two nonsmooth terms appeared in the
objective functions, thereby being of benefit for designing easily
implementable algorithms for the underlying separable models. A series of
computational experiments on RGB images and surveillance videos data sets
demonstrated that our approach performs better than some state-of-the-art
model-driven tensor completion approaches.

Declaration of Competing Interest: The authors declared that they have no
known competing financial interests or personal relationships that could have
appeared to influence the work reported in this paper.

## Acknowledgments

The authors are grateful to the editor and two anonymous referees for their
close reading and valuable comments, which led to great improvements of the
paper. They also would like to thank all authors of [44, 39, 12, 48, 58, 53,
59, 50] for sharing their code, especially thank Dr. Yufan Li and Mr. Zhiyuan
Zhang for their kind help on our experiments. C. Ling and H. He were supported
in part by National Natural Science Foundation of China (Nos. 11971138 and
11771113) and Natural Science Foundation of Zhejiang Province (Nos.
LY19A010019 and LD19A010002).

## References

  * [1] N. Komodakis, “Image completion using global optimization,” in _Computer Vision and Pattern Recognition_ , vol. 1, 2006, pp. 442–452.
  * [2] N. Hao, M. Kilmer, K. Braman, and R. Hoover, “Facial recognition using tensor-tensor decompositions,” _SIAM J. Imaging Sci._ , vol. 6, no. 1, pp. 437–463, 2013.
  * [3] A. Criminisi, P. Perez, and K. Toyama, “Region filling and object removal by exemplar-based image inpainting,” _IEEE Trans. Image Process._ , vol. 13, no. 9, pp. 1200–1212, 2004.
  * [4] X. Geng, K. Smith-Miles, Z. Zhou, and L. Wang, “Face image modeling by multilinear subspace analysis with missing values,” _Proceedings of the 17th ACM international conference on Multimedia_ , 2009.
  * [5] A. Efros and T. Leung, “Texture synthesis by non-parametric sampling,” in _Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on_ , 1999, pp. 1033–1038.
  * [6] D. Coupier, A. Desolneux, and B. Ycart, “Image denoising by statistical area thresholding.” in _Mustererkennung, 21 Dagm-symposium, Bonn, September_ , 1999.
  * [7] G. Golub and C. Van Loan, _Matrix Computations_ , 4th ed. Baltimore: The Johns Hopkins University Press, 2013.
  * [8] Q. Song, H. Ge, J. Caverlee, and X. Hu, “Tensor completion algorithms in big data analytics,” _ACM Trans. Knowl. Discovery Data_ , vol. 13, pp. 1–48, 2019.
  * [9] J. Liu, P. Musialski, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 35, no. 1, pp. 208–220, 2013.
  * [10] S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” _Inverse Probl._ , vol. 27, p. 025010, 2011.
  * [11] C. Lu, J. Feng, Z. Lin, and S. Yan, “Exact low tubal rank tensor recovery from Gaussian measurements,” in _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18_. International Joint Conferences on Artificial Intelligence Organization, 7 2018, pp. 2504–2510.
  * [12] P. Zhou, C. Lu, Z. Lin, and C. Zhang, “Tensor factorization for low-rank tensor completion,” _IEEE Trans. Image Process._ , vol. 27, no. 3, pp. 1152–1163, 2018.
  * [13] Y. Chen, C. Hsu, and H. Liao, “Simultaneous tensor decomposition and completion using factor priors,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 36, no. 3, pp. 577–591, 2014.
  * [14] E. Candès and B. Recht, “Exact matrix completion via convex optimization,” _Found. Comput. Math._ , vol. 9, no. 6, pp. 717–772, 2009\.
  * [15] C. Hillar and L. Lim, “Most tensor problems are NP-hard,” _J. ACM_ , vol. 6, pp. 1–39, 2013.
  * [16] T. Kolda and B. Bader, “Tensor decompositions and applications,” _SIAM Rev._ , vol. 51, pp. 455–500, 2009.
  * [17] I. Oseledets, “Tensor-train decomposition,” _SIAM J. Sci. Comput._ , vol. 33, no. 5, pp. 2295–2317, 2011.
  * [18] T. Jiang, T. Huang, X. Zhao, T. Ji, and L. Deng, “Matrix factorization for low-rank tensor completion using framelet prior,” _Inf. Sci._ , vol. 436-437, pp. 403–417, 2018.
  * [19] K. Hosono, S. Ono, and T. Miyata, “Weighted tensor nuclear norm minimization for color image denoising,” in _2016 IEEE International Conference on Image Processing (ICIP)_ , 2016, pp. 3081–3085.
  * [20] L. Huang, H. So, Y. Chen, and W. Wang, “Truncated nuclear norm minimization for tensor completion,” in _IEEE Sensor Array and Multichannel Signal Processing Workshop_ , 2014.
  * [21] J. Bengua, H. Phien, H. D. Tuan, and M. Do, “Efficient tensor completion for color image and video recovery: Low-rank tensor train,” _IEEE Trans. Image Process._ , vol. 26, no. 5, pp. 2466–2479, 2017.
  * [22] T. Y. Ji, T. Z. Huang, X. L. Zhao, T. H. Ma, and G. Liu, “Tensor completion using total variation and low-rank matrix factorization,” _Inf. Sci._ , vol. 326, pp. 243–257, 2016.
  * [23] J. Xue, Y. Zhao, W. Liao, and J. C. Chan, “Nonconvex tensor rank minimization and its applications to tensor recovery,” _Inf. Sci._ , vol. 503, pp. 109–128, 2019.
  * [24] Z. Zhang and S. Aeron, “Exact tensor completion using t-SVD,” _IEEE Trans. Signal Process._ , vol. 65, no. 6, pp. 1511–1526, 2017.
  * [25] C. Lu, J. Feng, Y. Chen, W. Liu, Z. Lin, and S. Yan, “Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization,” _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 5249–5257, 2016.
  * [26] C. Lu, J. Feng, Y. Chen, W. Liu, Z. Lin, and S. Yan “Tensor robust principal component analysis with a new tensor nuclear norm,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 42, pp. 925–938, 2020.
  * [27] M. Yuan and C. Zhang, “On tensor completion via nuclear norm minimization,” _Found. Comput. Math._ , vol. 16, pp. 1031–1068, 2016.
  * [28] M. Kilmer and C. Martin, “Factorization strategies for third-order tensors,” _Linear Algebra Appl._ , vol. 435, no. 3, pp. 641–658, 2011.
  * [29] Q. Zhao, L. Zhang, and A. Cichocki, “Bayesian CP factorization of incomplete tensors with automatic rank determination,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 37, no. 9, pp. 1751–1763, 2015.
  * [30] M. Filipović and A. Jukić, “Tucker factorization with missing data with application to low-n-rank tensor completion,” _Multidim. Syst. Sign. Process._ , vol. 26, no. 3, pp. 677–692, 2015.
  * [31] T. Yokota, Q. Zhao, and A. Cichocki, “Smooth PARAFAC decomposition for tensor completion,” _IEEE Trans. Signal Process._ , vol. 64, no. 20, pp. 5423–5436, 2016.
  * [32] Y. Wu, H. Tan, Y. Li, J. Zhang, and X. Chen, “A fused CP factorization method for incomplete tensors,” _IEEE Trans. Neural. Netw Learn. Syst._ , vol. 30, no. 3, pp. 751–764, 2019.
  * [33] X. Lin, M. Ng, and X. Zhao, “Tensor factorization with total variation and tikhonov regularization for low-rank tensor completion in imaging data,” _J. Math. Imaging Vis._ , vol. 62, pp. 900–918, 2020.
  * [34] Y. Liu, F. Shang, W. Fan, J. Cheng, and H. Cheng, “Generalized higher order orthogonal iteration for tensor learning and decomposition,” _IEEE Trans. Neural. Netw Learn. Syst._ , vol. 27, no. 12, pp. 2551–2563, 2016.
  * [35] L. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” _Physica D_ , vol. 60, pp. 227–238, 1992.
  * [36] V. Varghees, M. Manikandan, and R. Gini, “Adaptive mri image denoising using total-variation and local noise estimation,” in _Proceedings of the 2012 International Conference on Advances in Engineering, Science and Management (ICAESM)_ , 2012, pp. 506–511.
  * [37] M. Qin, Z. Li, S. Chen, Q. Guan, and J. Zheng, “Low-rank tensor completion and total variation minimization for color image inpainting,” _IEEE Access_ , vol. 8, pp. 53 049–53 061, 2020.
  * [38] X. Zhao, X. Nie, Y. Zheng, T. Ji, and T. Huang, “Low-rank tensor completion via tensor nuclear norm with hybrid smooth regularization,” _IEEE Access_ , vol. 7, pp. 131 888–131 901, 2019.
  * [39] F. Jiang, X. Liu, H. Lu, and R. Shen, “Anisotropic total variation regularized low-rank tensor completion based on tensor nuclear norm for color image inpainting,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2018, pp. 1363–1367.
  * [40] D. Qiu, M. Bai, M. Ng, and X. Zhang, “Robust low-rank tensor completion via transformed tensor nuclear norm with total variation regularization,” _Neurocomputing_ , vol. 435, pp. 197–215, 2021.
  * [41] Y. Wang, C. Xu, S. You, C. Xu, and D. Tao, “DCT regularized extreme visual recovery,” _IEEE Trans. Image Process._ , vol. 26, pp. 3360–3371, 2018.
  * [42] Y. Abe and Y. Iiguni, “Image restoration from a downsampled image by using the DCT,” _Signal Processing_ , vol. 87, pp. 2370–2380, 2007.
  * [43] Y. Du, G. Han, Y. Quan, Z. Yu, H. Wong, C. L. P. Chen, and J. Zhang, “Exploiting global low-rank structure and local sparsity nature for tensor completion,” _IEEE Trans. Cybern._ , vol. 49, no. 11, pp. 3898–3910, 2019.
  * [44] Z. Han, C. Leung, L. Huang, and H. So, “Sparse and truncated nuclear norm based tensor completion,” _Neural Process. Lett._ , vol. 45, pp. 729–743, 2017.
  * [45] Y. Li, L. Shen, and B. Suter, “Adaptive inpainting algorithm based on DCT induced wavelet regularization,” _IEEE Trans. Image Process._ , vol. 22, pp. 752–763, 2013.
  * [46] B. Madathil and S. George, “DCT based weighted adaptive multi-linear data completion and denoising,” _Neurocomputing_ , vol. 318, pp. 120–136, 2018\.
  * [47] Y. Wang and Q. Zhu, “Signal loss recovery in DCT-based image and video codecs,” in _Visual Communications and Image Processing ’91: Visual Communication_ , K.-H. Tzou and T. Koga, Eds., vol. 1605, International Society for Optics and Photonics. SPIE, 1991, pp. 667–678.
  * [48] T. Jiang, M. Ng, X. Zhao, and T. Huang, “Framelet representation of tensor nuclear norm for third-order tensor completion,” _IEEE Trans. Image Process._ , vol. 29, pp. 7233–7244, 2020.
  * [49] T. Jiang, X. Zhao, H. Zhang, and M. Ng, “Dictionary learning with low-rank coding coefficients for tensor completion,” _IEEE Trans. Neural. Netw Learn. Syst._ , 2021.
  * [50] X. Zhao, W. Xu, T. Jiang, Y. Wang, and M. Ng, “Deep plug-and-play prior for low-rank tensor completion,” _Neurocomputing_ , vol. 400, pp. 137–149, 2020\.
  * [51] R. Chartrand, “Shrinkage mappings and their induced penalty functions,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014, pp. 1026–1029.
  * [52] R. Chartrand, “Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data,” in _2009 IEEE International Symposium on Biomedical Imaging: From Nano to Macro_ , 2009, pp. 262–265.
  * [53] K. Shang, Y. Li, and Z. Huang, “Iterative p-shrinkage thresholding algorithm for low Tucker rank tensor recovery,” _Inf. Sci._ , vol. 482, pp. 374–391, 2019.
  * [54] S. Gaïffas and G. Lecué, “Weighted algorithms for compressed sensing and matrix completion,” 2011, https://arxiv.org/abs/1107.1638.
  * [55] C. Lu, J. Tang, S. Yan, and Z. Lin, “Nonconvex nonsmooth low rank minimization via ititerative reweighted nuclear norm,” _IEEE Trans. Image Process._ , vol. 25, pp. 829–839, 2016.
  * [56] J. Woodworth and R. Chartrand, “Compressed sensing recovery via nonconvex shrinkage penalties,” _Inverse Probl._ , vol. 32, pp. 075004, 2016.
  * [57] T. Oh, Y. Tai, J. Bazin, H. Kim, and I. Kweon, “Partial sum minimization of singular values in robust PCA: Algorithm and applications,” _IEEE Trans. Image Process._ , vol. 38, pp. 744–758, 2016.
  * [58] Y. Zheng, T. Huang, X. Zhao, T. Jiang, and T. Ma, “Tensor n-tubal rank and its convex relaxation for low-rank tensor recovery,” _Information Sciences._ , vol. 532, pp. 170–189, 2020.
  * [59] Y. Zheng, T. Huang, T. Ji, X. Zhao, T. Jiang, and T. Ma, “Low-rank tensor completion via smooth matrix factorization,” _Appl. Math. Model._ , vol. 70, pp. 677–695, 2019.
  * [60] Z. Wang, A. Bovik, H. Sheikh, E. Simoncelli, “Image quality assessment: From error visibility to structural similarity”, _IEEE Trans. Image Process._ , vol. 13, pp. 600–612, 2004.