Abstract
Let us consider a case where all of the elements in some continuous slices are missing in tensor data. In this case, the nuclear-norm and total variation regularization methods usually fail to recover the missing elements. The key problem is capturing some delay/shift-invariant structure. In this study, we consider a low-rank model in an embedded space of a tensor. For this purpose, we extend a delay embedding for a time series to a "multi-way delay-embedding transform" for a tensor, which takes a given incomplete tensor as the input and outputs a higher-order incomplete Hankel tensor. The higher-order tensor is then recovered by Tucker-based low-rank tensor factorization. Finally, an estimated tensor can be obtained by using the inverse multiway delay embedding transform of the recovered higherorder tensor. Our experiments showed that the proposed method successfully recovered missing slices for some color images and functional magnetic resonance images.
Introduction
Matrix/tensor completion is a technique for recovering the missing elements in incomplete data and it has become a very important method in recent years [2, 3, 1, 9, 16, 21, 4, 31, 30] . In general, completion is an ill-posed problem without any assumptions. However, if we have useful prior knowledge or assumptions regarding the data structure, completion can be treated as a well-posed optimization problem, such as convex optimization. The assumption of the structure is also referred to as a "model."
Introduction
The methods for modeling matrices/tensors can be categorized into two classes. In the first class, the methods directly represent data with the matrices/tensors themselves and some structures of the matrices/tensors are assumed, such as low-rank [2, 3, 1, 9, 16] and smooth properties [32, 11] . By contrast, the methods in the second class "embed" the data into a high-dimensional feature space and it is assumed that the data can be represented by low-rank or a smooth manifold in the embedded space [17, 25, 6, 18 ] (see Figure 1 ). Typically, a time series is represented by a "Hankel matrix" (see Section 2.1.1) and its low-rank property has been employed widely for modeling a linear time-invariant system of signals [25, 18] . For example, Li et al. [15] proposed a method for modeling damped sinusoidal signals based on a low-rank Hankel approximation. Ding et al. [6] proposed the use of rank minimization of a Hankel matrix for the video inpainting problem by assuming an autoregressive moving average model. Figure 2 shows an example of occlusion recovery for a noisy time series, which indicates that total variation (TV) and quadratic variation (QV) regularization methods reconstruct a flat estimator, whereas minimization of the Hankel matrix (our proposed method) successfully reconstructs the signal.
Introduction
In the proposed method, the incomplete input data are not represented as a Hankel matrix, but instead they are represented as a "higher order Hankel tensor" via multiway embedding with delay/shift along the time/space axes, and we solve the low-rank tensor completion problem in the embedded space. The minimization of the rank of a matrix/tensor is NP-hard [10] and the problem is often relaxed to nuclear-norm minimization [20] . A disadvantage of the relaxation to nuclear norm minimization is that it decreases the rank of the resultant matrix/tensor as well as the total component values in the matrix/tensor. In particular, nuclear norm minimization often obtains "dark" signals in denoising tasks. Thus, we employ Tucker decomposition for low-rank modeling of the higher order Hankel tensor completion.
Introduction
The Tucker-based tensor completion is a non-convex optimization problem, and the existing methods usually have difficulty for selecting the step-size parameter. In this study, we propose to use an auxiliary function-based approach, where it improves the convergence characteristics of the optimization process. Moreover, we propose a rank increment scheme for determining the appropriate multi-linear tensor A time series signal x(t) can be embedded into a threedimensional space with individual axes of x(t), x(t + 1), and x(t + 2). Clearly, most of the points are located on some hyper-plane (i.e., low-rank) in the embedded space. ranks. According to our extensive experiments, the proposed method is highly suitable for tensor completion (e.g. recovery of "Lena" from only 1% of the randomly sampled voxels) and it outperforms state-of-the-art tensor completion methods.
Notations
A vector is denoted by a bold small letter a ∈ R I . A matrix is denoted by a bold capital letter A ∈ R I×J . A higherorder (N ≥ 3) tensor is denoted by a bold calligraphic letter A ∈ R I1×I2×···×I N . The ith entry of a vector a ∈ R I is denoted by a i , and the (i, j)th entry of a matrix A ∈ R I×J is denoted by a ij . The (i 1 , i 2 , ..., i N )th entry of an N th-order tensor A is denoted by a i1i2···i N , where i n ∈ {1, 2, ..., I n } and n ∈ {1, 2, ..., N }. The Frobenius norm of an N th-order tensor is defined by ||X ||
Notations
A mode-k unfolding (matricization) of a tensor X is denoted as X (k) ∈ R I k ×Π n =k In . A mode-k multiplication between a tensor X ∈ R I1×I2×···×I N and a ma-
Notations
where the entries are given by
Notations
If we consider N matrices U (n) ∈ R In×Rn and an Nth order tensor G ∈ R R1×R2×···×R N , then the multi-linear tensor product is defined as
Notations
Moreover, a multi-linear tensor product excluding the n-th mode is defined as
Notations
When we consider Tucker decomposition, G and U (n) in Eq. (1) are referred to as the core tensor and factor matrices, respectively.
Proposed method
In this study, we assume a low-rank structure of a higher order Hankel tensor given by the MDT, which is defined in Section 2.1. We denote this by H(·). The proposed method is conceptually quite simple where it comprises three steps: (1) MDT, (2) low-rank tensor approximation, and (3) inverse MDT.
Proposed method
Let T ∈ R I1×···×I N and Q ∈ {0, 1} I1×···×I N be the input incomplete tensor and its mask tensor, respectively, and the first step is given by
Proposed method
where M ≥ N . In the second step, we obtain a low-rank approximation of T H based on the Tucker decomposition model. For example, we first consider the following optimization problem:
Proposed method
where R m ≤ J m (∀m). Finally, the resultant tensor can be obtained by the inverse MDT of Tucker decomposition:
Proposed method
2.1. MDT
Standard delay embedding transform
In this section, we explain the delay embedding operation. For simplicity, we first define a standard delay embedding transform for a vector, which can be interpreted as a time-series signal. Let us consider a vector
Standard delay embedding transform
, a standard delay embedding transform of v with τ is given by
Standard delay embedding transform
Thus, a standard delay embedding transform produces a duplicated matrix from a vector, where this is also referred to as "Hankelization" since
Standard delay embedding transform
then the standard delay embedding transform can be obtained by
Standard delay embedding transform
where
Standard delay embedding transform
is a folding operator from a vector to a matrix.
Standard delay embedding transform
Next, we consider an inverse transform of standard delay embedding. The forward transform can be decomposed into duplication and folding, so the inverse transform can also be decomposed into the individual corresponding inverse transforms: a vectorization operation and the MoorePenrose pseudo-inverse S † := (S T S) −1 S T . Thus, the inverse delay embedding transform for a Hankel matrix V H can be given by Figure 3 shows an example of the delay embedding transform for a vector, duplication matrix, and its inverse transform. We can see that the duplication matrix comprises multiple identity matrices. It should be noted that the diagonal elements of (S T S) comprise the numbers of duplications for individual elements, which are usually τ , but low for marginal elements.
Tensor extension
We now define the MDT for an N -th order tensor X ∈ R I1×I2×···×I N . The MDT of X with τ ∈ N N is defined by
Tensor extension
where fold (I,τ ) :
Tensor extension
constructs a 2N -th order tensor from the input N -th order tensor. In a similar manner to how the vector delay-embedding is a combination of linear duplication and folding operations, the MDT is also a combination of multi-linear duplication and multiway folding operations. Figure 4 shows flowcharts to illustrate single-way and multi-way delay embedding for a matrix. Finally, the inverse MDT for a Hankel tensor X H is given by
Tensor extension
where unfold (I,τ ) = fold
Tucker decomposition algorithms
In this section, we explain the algorithm for solving Problem (5). It should be noted that Problem (5) is not convex, its solution is not unique, and it is not easy to obtain its global solution [13] . In the case of Tucker decomposition without missing elements, it is known that the alternating least squares (ALS) [5] can efficiently obtain its stationary point. In the case with missing elements, algorithms for obtaining solutions have been proposed that use the gradient descent method [8] and manifold optimization [14, 12] in recent years. Gradient descent is usually slow to converge and manifold optimization can accelerate it by correcting its update direction on the manifold. However, a common issue with both methods is step-size parameter selection because the convergence time is sensitive to the step-size parameter.
Tucker decomposition algorithms
We also propose to use an "auxiliary function" based approach to perform Tucker decomposition with missing elements. The proposed algorithm is very simple but efficient because the ALS can be incorporated and it has no adjusting parameters. First, we define the original cost function and auxiliary function by
Tucker decomposition algorithms
where θ = {G, U (1) , ..., U (M ) } is a set of parameters, Q H = 1 − Q H represents a complement set of Q H , and X θ = G × {U } is a Tucker decomposition. Clearly, we have
Tucker decomposition algorithms
Let us consider the following algorithm
Tucker decomposition algorithms
where the cost function is monotonically non-increasing since we have
Tucker decomposition algorithms
It should be noted that θ k+1 only has to satisfy h(θ k |θ k ) ≥ h(θ k+1 |θ k ) to have a non-increasing property. Furthermore, the auxiliary function can be transformed by
Tucker decomposition algorithms
where
Tucker decomposition algorithms
Thus, the minimization of the auxiliary function itself can be regarded as the standard Tucker decomposition without missing elements, which can be solved efficiently using the ALS.
Tucker decomposition algorithms
In practice, the proposed algorithm comprises the following two steps: (1) calculate the auxiliary tensor by
Tucker decomposition algorithms
and (2) update G and {U (m) } M m=1 using the ALS [5] to optimize X ← G × {U }; end for 10:
Tucker decomposition algorithms
The orthogonality constraint for each U (m) supports the uniqueness of the solution for Tucker decomposition and it does not change the reconstructed tensor from the original optimization problem. Finally, the proposed Tucker-based tensor completion is summarized in Algorithm 1. Algorithm 1 updates U (m) and G for only one cycle of the ALS, and it does not achieve a strict minimization of the auxiliary function. However, it is guaranteed to decrease the auxiliary function because each update obtains the global minimum of the sub-optimization problem of (20) with respect to the corresponding parameter. Thus, Algorithm 1 still has the monotonic convergence property.
Tucker decomposition with rank increment
A difficult and important issue with the Tucker-based tensor completion method is determining an appropriate rank setting (R 1 , ..., R M ). If we aim to obtain the lowest rank setting for sufficient approximation, the rank estimation problem can be considered as
Tucker decomposition with rank increment
where is a noise threshold parameter. However, we do not know the existence of the unique solution (R * 1 , ..., R * M ) for Problem (21) and it will be dependent on . Furthermore, even if the best rank setting is unique, the resultant low-rank tensor X * is not unique. To address this issue, we propose the use of a very important strategy called the "rank increment" method. Figure 5 provides a flowchart to illustrate the concept of Tucker decomposition with/without rank increment. The rank increment strategy has been discussed in several studies of matrix and tensor completion [19, 7, 22, 24, 27, 30] , but the present study is its first application to Tucker-based completion to the best of our knowledge. The main reason for using the rank increment method is the non-uniqueness of the solution for the tensor X . Thus, the resultant tensor depends on its initialization. The main feature of the rank increment method is that the tensor should be initialized by a lower rank approximation than its target rank. Based on this strategy, the proposed algorithm can be described as follows.
Tucker decomposition with rank increment
• Step 1: Set initial R m = 1 for all m.
Tucker decomposition with rank increment
• Step 2: Obtain G and
Tucker decomposition with rank increment
with (R 1 , ..., R M ) using Algorithm 1 and obtain X = G × {U }.
Tucker decomposition with rank increment
• Step 3: Check the noise condition ||Q H (T H − X )|| 2 F ≤ , where the algorithm is terminated if it is satisfied; otherwise, go to the next step.
Tucker decomposition with rank increment
• Step 4: Choose the incremental mode m and increment R m , and then go back to step 2.
Tucker decomposition with rank increment
The problem is how to choose m and how to increase the rank R m . We propose choosing m using the "m-th mode residual" of the cost function, which is defined as a residual on the multi-linear subspace spanned by all the factor matrices excluding the m-th mode factor. This is mathematically formulated as:
Tucker decomposition with rank increment
We can interpret this as meaning that the selected m -th mode has a high expectation of cost reduction when R m increases while the other-mode ranks remain fixed. For the rank increment process, we consider the rank sequences for individual modes. For example, the rank sequence for the m-th mode is set as L m = [1, 2, 4, 8, ..., J m ] because the contribution rates of the singular vectors usually decrease exponentially. Thus, a small rank increment is important for the phase of a low-rank approximation, whereas a small rank increment is not effective for the phase of a relatively high-rank approximation. Large rank steps for the high-rank phase help to accelerate the algorithm, but they should be selected carefully because excessively large rank steps may lead to problems with non-unique solutions. The Algorithm 2 Tucker-based tensor completion with rank increment X ← G × {U }; 8:
Tucker decomposition with rank increment
if |f 2 − f 1 | ≤ tol then 10:
Tucker decomposition with rank increment
12:
Tucker decomposition with rank increment
13:
Tucker decomposition with rank increment
15:
Tucker decomposition with rank increment
proposed method for Tucker-based tensor completion with rank increment is summarized in Algorithm 2.
Experiments

Verification of the proposed method using a typical color image
First, in our experiments, we tried to fill the missing slices in a typical color image by using MDT and fixed rank Tucker decomposition. The input image is depicted in Figure 5 . We set τ = (32, 32, 1) and a (256, 256, 3) color image was converted into a (32, 225, 32, 225, 1, 3) tensor. The fifth mode can be ignored so this Hankel tensor was regarded as a fifth-order tensor with a size of (32, 225, 32, 225, 3) . Figure 6 shows the images obtained with various settings for the rank parameter. Clearly, lowrank Tucker decomposition with the Hankel tensor successfully filled the missing area. However, an important issue is how to treat the difference between the meanings of (R 1 , R 3 ) and (R 2 , R 4 ). The fundamental difference between (R 1 , R 3 ) and (R 2 , R 4 ) is due to the window sizes of 32 and 225. Thus, it should be noted that a lower (R 1 , R 3 ) may contribute to the representation of the local structure (e.g., smoothness), whereas a lower (R 2 , R 4 ) may contribute to the representation of the global structure (e.g., recursive textures) of the image. In Figure 6 , when we compare two flows from the bottom right to the top right, and from the bottom right to the bottom left, the low-rankness of (R 2 , R 4 ) is clearly more important than that of (R 1 , R 3 ) for recovering the missing area. Next, we tried to fill missing color images using MDT and Tucker decomposition with the rank increment method. The rank sequences for the proposed method were set as L 1 = L 3 = (1, 2, 4, 8, 16, 24, 32 ), L 2 = L 4 = (1, 2, 4, 8, 16, 32, 64, 96, 128, 160, 192, 225) , and L 5 = 3. Figure 7 shows the main flow for the processed images using the proposed method. Using the rank increment method, we first obtained a Tucker decomposition with a very lowrank setting (e.g., rank-one tensor) and a higher-rank decomposition was then obtained by using the previous lowerrank decomposition for its initialization. We repeatedly obtained a higher-rank decomposition until the residual was sufficiently small. Thus, the rank increment method automatically selected an appropriate rank setting.
Comparison using color images
We compared the performance of the proposed method with those of state-of-the-art tensor completion algorithms: HaLRTC (nuclear-norm regularization) [16] , TV regularization [32] , nuclear-norm and TV regularization (LR&TV) [28] , STDC (constrained Tucker decomposition) [4] , and SPCQV (constrained PARAFAC tensor decomposition) [30] . We prepared six missing images for this experiment. The first image had 11 continuous missing slices along the vertical axis. Several horizontal and vertical slices and many voxels were missing from the second image. Random vertical and horizontal slices were missing from the third and fourth images. In addition, 95% and 99% of the random voxels were missing from the fifth and sixth images, respectively. Figure 8 shows the experimental results obtained after the completion of various incomplete images. Magnified regions are depicted at the bottom right in the first to fourth images. HaLRTC recovered random missing voxels for the second image, but it failed to recover the missing slices for all of the images. The TV regularization and LR&TV regularization methods filled the missing areas, but the recovered areas were unnaturally flat. STDC failed to recover the missing slices and SPCQV retained "shadows" of the missing slices. By contrast, the proposed method recovered most of the missing slices without shadows. For the image with 95% missing voxels, the proposed method and SPCQV obtained similar results. However, for the image with 99% missing voxels, the result obtained by the proposed method was much better than that by SPCQV. Table 1 shows the peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) [26] for these comparisons, where the best PSNR and SSIM values are emphasized in bold font. According to this quantitative evaluation, the proposed method performed better than the state-of-the-art methods in terms of the PSNR, and the results in terms of the SSIM were very competitive with SPCQV for some of the images. Six missing color images were artificially generated comprising: slice missing case "facade 1," slice+voxel missing case "facade 2," random slice missing cases "house' and "peppers," and random voxel missing cases "Lena (95%)' and "Lena (99%)'. 
Comparison using fMRI images
In the next experiment, we tried to recover continuous missing time frames in fMRI images. Figure 9 shows the image prepared with missing data. There were 94 time frames of the fMRI slices and one to five continuous time frames were removed. The size of the tensor was (64 × 64 × 94). We applied the proposed method with τ = (2, 2, 32) for the given tensor. The rank sequences were set as 2, 4, 8, 16, 32, 63) , and L 5 = (1, 2, 4, 8, 16, 32 ). Figure 10 shows the results of this experiments. Similar to the color image experiments, the ordinary low-rank Table 2 shows the signal-to-noise ratio (SNR) and mean SSIM results obtained for all of the completion methods, which demonstrates that the proposed method performed better than the state-of-the-art methods in terms of the mean SSIM measure and it was also very competitive in terms of the SNR. The idea of tensor completion using MDT and its inverse transform is novel. Most of the existing methods for tensor completion are based on structural assumptions in the signal space, such as nuclear-norm regularization and TV regularization. By contrast, our method considers a structural assumption in the embedded space, which can be regarded as a novel strategy for the tensor completion problem. Furthermore, we employ delay-embedding in this approach and it is extended it in a multi-way manner for tensors.
An auxiliary function-based approach for Tucker decomposition of a tensor with missing elements
The auxiliary function-based algorithm for Tucker decomposition is efficiently employed. The existing algorithms used for the Tucker decomposition of a tensor with missing elements [8, 14, 12] are based on gradient methods. However the convergence speed of the gradient method is quite sensitive to the step-size parameter. By contrast, the proposed algorithm does not have any hyper-parameters and its monotonic convergence is guaranteed by the auxiliary function theory.
Model selection and uniqueness improvement by the rank increment method
The rank increment method for the Tucker decomposition of incomplete tensors is firstly applied in the best of our knowledge. Several methods for estimating multi-linear tensor ranks have been studied only for complete tensors [23, 29] . Methods for estimating the ranks of matrix and PARAFAC decompositions have been proposed for incomplete data [22, 24, 27, 30] , but these methods cannot be applied to our problem. Thus, we proposed a new method for estimating multi-linear ranks for an incomplete tensor, where it can also handle the issue of non-unique solutions.
Computational bottleneck
The proposed method has an issue with data volume expansion due to MDT. An N -th order tensor is converted into a 2N -th order tensor by MDT and its data size increases roughly N n=1 τ n -fold. This issue makes it difficult to apply the proposed method to large-scale tensors and this problem will be addressed in future research.
Conclusions
In this study, we proposed a novel method and algorithm for tensor completion problems that include missing slices. The recovery of missing slices is recognized as a difficult problem that ordinary tensor completion methods usually fail to solve. To address this problem, we introduced the concept of "delay embedding" from the study of dynamical systems and extended it for our problem. We showed that missing slices can be recovered by considering lowrank models in embedded spaces and that MDT is a good choice for this purpose.
Conclusions
At present, the proposed method is very basic but it has many potential extensions such as using different embedding transformations and constrained tensor decompositions (e.g., non-negative, sparse, and smooth). The MAT-LAB code will be available via our website 1 .

{'paper_id': '4600570', 'title': 'Missing Slice Recovery for Tensors Using a Low-Rank Model in Embedded Space', 's2_url': 'https://api.semanticscholar.org/CorpusID:4600570', 'source': 'S2ORC'}