A New Low-Rank Learning Robust Quaternion Tensor Completion Method for Color Video Inpainting Problem and Fast Algorithms

Let $\mathbb{Q}$ denotes the set of quaternion and a quaternion ${\bf a}$ has one real part $a_{0}\in\mathbb{R}$, three imaginary parts $a_{1},a_{2},a_{3}\in\mathbb{R}$ and is expressed as ${\bf a}=a_{0}+a_{1}{\bf i}+a_{2}{\bf j}+a_{3}{\bf k},{\bf i}^{2}={\bf j}^{2}={\bf k}^{2}={\bf i}{\bf j}{\bf k}=-1$ [5]. A symbol of boldface is used to express quaternion scalar, vector, matrix or tensor. A quaternion matrix ${\bf A}=A_{0}+A_{1}{\bf i}+A_{2}{\bf j}+A_{3}{\bf k}\in\mathbb{Q}^{m\times n}$ with $A_{0},\ldots,A_{3}\in\mathbb{R}^{m\times n}$. If $A_{0}=0$ and $A_{1},A_{2},A_{3}\neq 0$, ${\bf A}$ is named by a purely imaginary quaternion matrix. The quaternion shrinkage function shrinkQ is defined in [8] by:

where $\tau>0$, $\texttt{absQ}({\bf A}):=[|{\bf a}_{ij}|]$ and

Suppose ${\bf A}={\bf U}\Sigma{\bf V}^{*}$ is the singular value decomposition and denote $\{\sigma_{j},{\bf u}_{j},{\bf v}_{j}\}$ by the singular triplets of a quaternion matrix ${\bf A}\in\mathbb{Q}^{m\times n}$. The quaternion singular thresholding function approxQ is defined in [8] by:

where $\sigma_{1}\geq\cdots\geq\sigma_{k}>\tau$ and the singular values $\sigma_{j}<\tau$ are substituted by zeros. Quaternion matrix norms are defined by $\left\|{\bf A}\right\|_{1}:=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}\left|{\bf a}_{ij}\right|$, $\left\|{\bf A}\right\|_{\infty}:=\max\limits_{i,j}\left|{\bf a}_{ij}\right|$, $\left\|{\bf A}\right\|_{F}=\sqrt{\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}\left|{\bf a}_{ij}\right|^{2}}:=\sqrt{\operatorname{Tr}\left({\bf A}^{*}{\bf A}\right)}$, and $\|{\bf A}\|_{*}:=\sum\limits_{i=1}^{r}\sigma_{i}$.

A low-rank quaternion matrix ${\bf L}_{0}$ can be recovered completely from an observed quaternion matrix ${\bf X}=\mathcal{P}_{\Omega}({\bf L}_{0}+{\bf S}_{0})$ by the RQMC method [10], where ${\bf S}_{0}$ is a noisy matrix and $\mathcal{P}_{\Omega}$ is a random sampling operator:

By [10, Theorem 2], if the sufficient conditions are satisfies, ${\bf L}_{0}$ can be exactly computed by solving the following minimization problem with $\lambda=\frac{1}{\rho n_{(1)}}$,

A practical QMC algorithm is given in [8, Supplementary Material]. The augmented Lagrangian function of (3) is defined by

where $\mu$ is the penalty parameter. The solving procedure is

Let $\boldsymbol{\mathcal{X}}\in{\mathbb{Q}}^{n_{1}\times n_{2}\times\cdots\times n_{k}}$ denotes observed quaternion tensor with missing and/or corrupted entries. Then the RQTC problem is mathematically modeled by the following minimization problem,

where $\boldsymbol{\mathcal{L}}$, $\boldsymbol{\mathcal{S}}$ $\in{\mathbb{Q}}^{n_{1}\times n_{2}\times\cdots\times n_{k}}$ denote the target low-rank tensor and the sparse data, respectively. The quaternion tensor random sampling operator $\mathcal{P}_{\Omega}$ is defined by

The quaternion tensor nuclear norm and the $\ell_{1}$ norm are defined by

where $\alpha_{j}$’s are constants satisfying $\alpha_{j}\geq 0$ and $\sum_{j=1}^{k}\alpha_{j}=1$. Here, the quaternion tensor nuclear norm is essentially a convex combination of quaternion matrix nuclear norms which are generated by unfolding the tensor along each mode. Notice that $\left\|{{\bf S}_{(1)}}\right\|_{1}=\left\|{{\bf S}_{(2)}}\right\|_{1}=\cdots=\left\|{{\bf S}_{(k)}}\right\|_{1}$.

To derive the exact RQTC theorem, we need to build the incoherence conditions of quaternion tensors.

The condition (10) strengthens the original quaternion matrix incoherence condition (9) and keeps balance between the ranks of quaternion $\boldsymbol{\mathcal{X}}$. Indeed, define $\kappa_{j}:=\frac{r_{j}}{n_{j}^{(2)}}$ and $\kappa:=\max{\kappa_{j}}$. Clearly, a larger $\kappa$ means that even though quaternion tensor $\boldsymbol{\mathcal{X}}$ has a certain mode of low-rank but also has a mode of high rank.

Introducing two auxiliary variables $\boldsymbol{\mathcal{P}}$ and $\boldsymbol{\mathcal{Q}}$, the augmented Lagrangian equation of problem (11) becomes

where $\beta_{j}$ and $\mu$ are penalty parameters, ${\bf Y}_{(j)}$ and ${\bf Z}_{(j)}$ are results of ‘unfold’ function (5) acted on two Lagrange multipliers $\boldsymbol{\mathcal{Y}}$ and $\boldsymbol{\mathcal{Z}}$ that are two quaternion tensors. Now, we design an optimization algorithm to solve (13) based on the ADMM framework. Problem (13) can be converted to two-block subproblems and each one contains two unknown variables:

$[\boldsymbol{\mathcal{S}},~{}\boldsymbol{\mathcal{P}}]$ subproblem:

$[\boldsymbol{\mathcal{L}},~{}\boldsymbol{\mathcal{Q}}]$ subproblem:

By these formulae, the minimization problems of quaternion tensors are equivalently converted into the minimization problems of quaternion matrices. It seems that they can be feasibly solved by the QMC iteration (4). However, one obstacle is the $\boldsymbol{\mathcal{L}}$ subproblem that contains a convex combination of quaternion matrix norms. Fortunately, we find that this problem has a closed-form solution.

The other three subproblems can be solved similarly. For instance, the $\boldsymbol{\mathcal{S}}$ subproblem can be solved by the shrinkage of quaternion operator shrinkQ (1), and in fact, it has a closed-form solution:

To summarize above analysis, we present a new RQTC algorithm in Algorithm 1 and prove its convergence in Theorem III.3.

In the above, we have presented a novel RQTC model with the exact recovery theorem and a new ADMM-based algorithm with a convergence proof. They are feasible and efficient to restore quaternion tensors from partial and/or corrupted entries under the condition that the assumption of Theorem III.1 is satisfied. However, the low-rank condition sometimes does not hold in practical applications. For instance, quaternion tensor that represents color video is of high-rank when color video contains high frequency information. So we need to improve our model and algorithm further.

Now we present an improved RQTC model by introducing a low-rank learning method. For the convenience of description, we concentrate on $3$-mode quaternion tensor $\boldsymbol{\mathcal{X}}\in\mathbb{Q}^{n_{1}\times n_{2}\times n_{3}}$ that represents color video and use the engineer language instead of the mathematician language.

Since color video is often of large-scale, we set a window for searching low-rank information and denote the part of quaternion tensor in this window by adding a subscript $t$. That is, $\boldsymbol{\mathcal{X}}_{t}$ denotes a small quaternion tensor of $\boldsymbol{\mathcal{X}}$ in a fixed searching window.

Suppose we set $p$ windows totally, in other words, we divide the large tensor into $p$ smaller ones. A $3$-mode quaternion tensor is a stack of horizontal, lateral and frontal slices. We choose a series of overlapping patches of $\boldsymbol{\mathcal{X}}_{t}$ (the $t$th searching window of tensor $\boldsymbol{\mathcal{X}}$) from three kinds of slices, respectively, and classify them into $\ell_{j}$ classes $(j=1,2,3)$. Then we vectorize each patch of the $s$th class ($1\leq s\leq\ell_{j}$) and rearrange them into a quaternion matrix, denoted by $\mathscr{F}_{s}^{j}(\boldsymbol{\mathcal{X}}_{t})$, In other words, $\mathscr{F}_{s}^{j}(\boldsymbol{\mathcal{X}}_{t})$ is a low-rank quaternion matrix generated by the $s$th class of similar patches from the $j$th type of slice. Define the classification function of similar patches by

The function is invertible and the inverse is defined by

Now we introduce a learning strategy into RQTC model and present a new low-rank learning robust quaternion tensor completion model (LRL-RQTC):

where $\mathscr{F}_{s}^{j}$ is a mapping transformation (15). Different from the prior NSS-QMC model that uses the distance function to search similar patches, here we introduce a new 2DQPCA-based classification function and propose a new LRL-RQTC model with adaptively low-rank learning. The model (17) is a minimization issue consisting of three subproblems and independent of each other. For the convenience of the narrative, we only present the operation on the frontal slice in the following part, i.e.

The flowchart of the patched-based learning method is shown in Fig. 1. Firstly, choose the $t$th window $(1\leq t\leq p)$ and get $n$ overlapping patches ${\bf Y}_{t}^{(i,j)}$ with size $w\times h$ ($0<w\leq n_{1}$, $0<h\leq n_{2}$), covering each frontal slice of $\boldsymbol{\mathcal{X}}_{t}$. Then we gather them into a set $\mathcal{G}_{t}$

where $(i,j)$ denotes the location of a patch. Secondly, we set $\ell$ exemplar patches which are non-overlapping. After choosing them, we calculate their eigen subspace ${\bf V}$. Then we find a number of patches most similar to the exemplar patches by classification in group $\mathcal{G}_{t}$. The entire process is shown in Algorithm 2. For the $s$th exemplar patch, similar patches are stored in $\hat{\mathcal{G}}_{s}(s=1,\cdots,\ell)$, which is the subset of $\mathcal{G}_{t}$. By the 2DQPCA technology, we successfully achieve better performance in matching similar patches by learning low dimensional representation and forming small scale and quantity matrices to reduce CPU time. According to the result of classification from 2DQPCA, the number of similar patches in $\hat{\mathcal{G}}_{s}$ is not fixed, denoted by $|\hat{\mathcal{G}}_{s}|=d_{s}$ with $d_{s}$ being a positive integer. Finally, we stack the quaternion matrix from $\hat{\mathcal{G}}_{s}$ to the quaternion column vector and put them together lexicographically to construct a new quaternion matrix

where ${\bf Y}_{t}^{(i_{k},j_{k})}$ denotes the $k$-th element of $\hat{\mathcal{G}}_{s}$. Thus, this 2DQPCA-based classification process learns $\ell$ small low-rank quaternion matrices stored in the set $\mathcal{F}(\boldsymbol{\mathcal{X}}_{t})$.

Then, we repeat the above learning process on each window of horizontal, lateral and frontal slices of tensor $\boldsymbol{\mathcal{X}}$ until the low-rank conditions are satisfied.