In the past decades, tensor completion has aroused increasing attention due to its wide applications in a variety of fields, such as computer vision [1]–[8], multi-relational link prediction [9]–[11], and recommendation system [12]–[15]. The goal of tensor completion is to recover an incomplete tensor from partially observed entries, and the most existing methods try to achieve it via the low-rank structure assumption. To our best knowledge, these tensor completion methods can mainly be categorized into tensor decomposition based method and rank-minimization based method.

Tensor decomposition based method aims to decompose the incompleted tensor into a sequence of low-rank factors and then predict the missing entries via the latent factors. For example, the CANDECOMP/PARAFAC (CP) decomposition based methods [16]–[21] recover the target tensor by a summation of component rank-one tensors, and the Tucker decomposition based methods [22]–[25] via a core tensor multiplied by a low-rank matrix along each mode. In recent years, the Tensor-Train and Tensor-Ring decompositions are commonly used to express the higher-order incomplete tensor by a multilinear product over a sequence of low-order latent cores [26]–[29]. Unfortunately, the tensor decomposition based method is non-convex, may suffer from the problem of local solutions. In addition, most of the tensor decomposition based methods require predefined rank, and their performance is rather sensitive to the rank selection. For the Tucker, TensorTrain, and Tensor-Ring decompositions, the rank is defined as a vector; it, therefore, requires a computational expensive cost to find the optimal rank due to the immense selections.

Rank-minimization based method is another type of approach to exploit the low-rank structure of incompleted tensor. Since the tensor rank minimization rankis an NP-hard problem, a number of norms are defined as the convex surrogates of tensor rank, and the most commonly used ones are overlapped nuclear norm [30]–[32] and latent nuclear norm [33], [34]. In [30], the overlapped nuclear norm via Tucker rank was first proposed by assuming all modes are low-rank, while it performs poorly when the target tensor is only low-rank in a certain mode. In contrast to the overlapped nuclear norm, the latent nuclear norm [33] generalizes better, especially for the tensor with only several modes low-rank. However, these two norm regularizers are based on the unbalanced mode-k unfolding scheme, and therefore the unfolding matrices are usually unbalanced. For a significantly-unbalanced matrix of size , the matrix rank substantially fails to capture the global information of the target tensor due to the small upper bound min{m, n}. Considering the powerful capacity of Tensor Train decomposition for representing higher-order tensors, the overlapped and latent nuclear norms via Tensor Train are proposed in [31] and [34], respectively. These two norms are still based on the unbalanced unfolding scheme, i.e., k-mode unfolding scheme (the first k modes versus the rest). Though the Tensor Ring nuclear norm [32] applied a more balance scheme to unfold the target tensor, a set of weighting-parameters are needed to carefully tune, which spent an expensive cost. Finally, the above-mentioned norm regularizers are commonly minimized by the alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) algorithms, where the computational expensive partial-SVD operation on a large dense matrix is usually required.

To address the above-mentioned drawbacks, this paper de-fines a new latent nuclear norm by using a more balanced unfolding scheme, which is shown more powerful over the other norm regularizers in exploiting the low-rank global information of the target tensor. It should be noted that, though we applied the same balanced unfolding scheme as the overlapped TR nuclear norm in the new norm, it needn’t additional weighting-parameters for the unfolding matrices. Moreover, instead of simply utilizing the expensive ADMM or BCD algorithms, the Frank-Wolfe (FW) algorithm is developed to minimize the proposed latent nuclear norm for tensor completion. Under the FW framework, we show that linear subproblem has a closed-form solution which can be obtained from the rank-one SVD, and most steps of the algorithm only need to access the observed entries. By utilizing sparsity of the observed tensor, we can only maintain the sparse tensor and small basis matrices instead of full-size tensors, thus require much smaller space in each iteration. Due to the proposed method operates on the sparse tensors and only need to perform rank-one SVD during iteration, it requires much smaller time-complexity over other tensor norms, which is discussed later. Furthermore, extensive experimental results of visual-data inpainting confirm that the proposed method is able to achieve state-of-the-art performance at smaller costs of time and space, which is very meaningful for the memory-limited equipment in practical applications. To sum up, the contributions of this paper are listed below:

• By using a more balanced unfolding scheme, a new latent nuclear norm is proposed, which is shown more powerful over other norm regularizers to exploit global information of the target tensor.

• An efficient method, i.e. the new latent nuclear norm together with the Frank-Wolfe algorithm, is developed for tensor completion, which requires much smaller complexity over other tensor norms in terms of space and time.

• The proposed method requires neither predefined rank nor additional weighting-parameters for the unfolding matrices and is empirically shown to achieve outstanding performance at smaller costs of time and space. This is very meaningful for the memory-limited equipment in practical applications. The rest of this paper is organized as follows. The related works are described in Section II. Notations and preliminaries required in this paper are introduced in Section III. In Section IV, we define a new latent nuclear norm and develop an efficient Frank-Wolfe based algorithm. Moreover, the complexities of time and space are also theoretically analyzed. In Section V, performance of the proposed method is investigated in synthetic data and real-world visual data. Finally, the work of this paper is concluded in section VI.

Our work is somewhat related to latent-norm based com- pletion methods [33], [34] and Tensor-Ring based completion methods [28], [32], [35]. In [33], Tomioka et al. proposed the latent nuclear norm by mode-k unfolding scheme (one mode versus the rest), and shown that it generalizes better than the overlapped nuclear norm [30] when only several modes are low-rank. Since the mode-k unfolding scheme is significantly-unbalanced, the unfolding matrix is usually unbalanced and the rank is often too small to describe the global information of target tensor. Recently, Wang et al. [34] defined a new latent nuclear norm via Tensor Train, however it may still base on the significantly-unbalanced matrix due to the unbalanced k-mode unfolding scheme. In recent years, Wang et al. [28] first applied Tensor Ring decomposition by alternating least square (TR-ALS) to incomplete data. Yuan et al. [35] proposed a method, named Tensor Ring low-rank factors (TRLRF), by combining nuclear norm regularization and TR decomposition. However, these two TR-decomposition based methods require a large computational complexity per iteration and thus may run out of the memory when encountering the large-scale data. Moreover, the TR-rank is defined as a vector and it is therefore very challenging to manually find the optimal rank due to the immense selections. In [32], Yu et al. defined an overlapped Tensor Ring nuclear norm by a more balanced unfolding scheme and showed that it substantially improves the recovery performance in visual-data inpainting. Unfortunately, its computational complexity is still large and a set of weighting-parameters require computational expensive tuning.

In contrast, the proposed latent nuclear norm is defined via a more balanced unfolding scheme and requires neither pre-defined rank nor additional weighting-parameters. Moreover, the new latent nuclear norm together with the FW algorithm is developed as an efficient method, which is shown more powerful to exploit global information at smaller costs of time and space.

A. Notations

This paper denotes scalars, vectors, and matrices by standard lowercase letters (e.g. x, y, z), boldface lowercase letters (e.g. x, y, z), and bold capital letters (e.g. X, Y, Z), respectively. A tensor of order N > 3 is denoted by Calligraphic letter, e.g. . or represents an element of the index . denotes a fiber along mode 1 and X(:, : a slice along mode 1 and mode 2, and so on. The inner product of X and Y of the same size is defined by , and the Frobe- nius norm of X can be calculated by .

B. Preliminaries

In this section, we briefly describe the Tensor Ring decomposition, Tensor Circular Unfolding, and their relation.

Tensor Ring decomposition [36], [37] is recently proposed to represent a higher-order tensor by a sequence of 3rd-order latent core tensors, i.e. TR-cores. Specifically, given an Nth-order tensor , the TR-cores can be denoted by and the TR-rank by the vector , where . Tensor Ring decomposition of X can be formally expressed by

where is the matrix trace operation. More details of Tensor Ring decomposition can be seen in [36], [37].

To efficiently exploit the global information of high-order tensors, Yu et al. [32], [38] defined a balance unfolding scheme named Tensor Circular Unfolding (TCU) in Definition 1 and described its relation with TR decomposition in Theorem 1.

Definition 1. (Tensor Circular Unfolding [32], [38]) Suppose an Nth-order tensor , the tensor circular

Fig. 1: Illustration of Tensor Ring representation of an 5th-order tensor and its Tensor Circular Unfoldings. Each node of denotes a tensor whose order decided by its number of edges. The edge connecting two nodes denotes a contraction between two tensors along a specific mode. The Tensor Circular Unfoldings are easily obtained by unfolding X along modes specified by a red arc.

unfolding matrix denoted by can be represented by

where d < N is a positive integer and

The d continuous modes enumerate the rows of , and the rest modes its columns. To easily understand the Tensor Circular Unfolding scheme, Fig. 1 illustrates the circularly-unfolding matrices obtained by unfolding X along modes specified by a red arc.

This theorem theoretically reveals the relation of Tensor Circular Unfolding scheme and Tensor Ring decomposition, which implies that the low-rank global information can be exploited by Tensor Circular Unfolding scheme.

A. Latent Tensor-Ring Nuclear Norm

As well-known, in tensor completion, most common definitions of the nuclear norm are overlapped nuclear norm and latent nuclear norm via Tucker/TT rank [30], [31], [33], [34]. These nuclear norms are based on mode-k unfolding scheme (one mode versus the rest) or k-modes unfolding scheme (the first k modes versus the rest), and thus may construct significantly-unbalanced unfoldings. For a significantly-unbalanced matrix of size , enough large rank is usually required to describe the global information, while it fails due to the small upper bound min{m, n}. Though TR nuclear norm [32] applied a more balanced unfolding scheme, i.e. Tensor Circular Unfolding (TCU), to exploit the global information and achieve a rather-well performance, its computational expensive selection of weighting-parameters seems inappropriate in practical applications. Moreover, we found that the performance of TR nuclear norm largely depends on the selection of its weighting-parameters. To solve the issues that the above mentioned nuclear norms have, a new nuclear norm named latent TR nuclear norm is defined as follow by using TCU scheme.

Definition 2. (Latent Tensor-Ring Nuclear Norm) Suppose an Nth-order tensor , the latent Tensor-Ring nuclear norm is

Note that, latent TR nuclear norm is defined as the infimum over N tensors which are respectively low-rank in the specific unfolding .

Therefore, a new tensor completion model via latent TensorRing nuclear norm is formulated as

where and are true tensor and reconstructed tensor, respectively. denotes the index set of the observed entries, so represents the observed entries from the true tensor. is the circularlyunfolded matrix with size where , . Since the balanced unfolding scheme does help to catch the global information, d is default set as

B. Frank-Wolfe Based Algorithm

Though the alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) are usually used to solve the nuclear norm based completion model, they have to operate on the full-size tensors and perform partialSVD during iterations [7], [30]–[32], [35], [39], [40]. This substantially requires large costs in time and space when encountering large-scale data. Similar to [11], this section instead develops the Frank-Wolfe [41], [42] based algorithm to solve the problem (5) by utilization of sparsity structure and rank-one SVD operation in each iteration, which will be shown much more efficient in time and space later. Under the Frank-Wolfe framework, we first transform (6) into

where is a tensor with if , and 0 otherwise. is a constraint parameter. Then we solve the problem (7) via the following three steps:

Linear subproblem of . For the linear subproblem, arg , Proposition 1 shows that the closed-form solution can be obtained efficiently from rank-one SVD.

Proposition 1. The closed-form solution of the linear problem arg can be given by

where arg denote a pair of left and right singular vectors corresponding to the largest singular value .

Proof. Let be the latent TR norm of S, then its dual norm can be defined as

From this definition and constraint , it is easy to get that

Note that, according to [33], the dual norm can be given by

where denotes the spectral norm, i.e., the greatest singular value of . Hence,

It is not difficult to find that the minimum of < is obtained when

Therefore, we can get fold.

Seen from the problem (7), it is easy to check that , and its rank-one SVD can be computed efficiently by the power method in [43].

Line search of . With F in problem (7), the step-size can be given by solving the following problem:

Note that the problem (14) is essentially a quadratic equation of , i.e.,

where , . Hence, it is easy to get a simple closed-form solution:

Update . Note that the update of only needs to access the entries indexed by , i.e., . Hence, instead of calculating and storing the full tensors during iterations, we can follow an efficiently update scheme proposed in [11]. This efficiently update scheme consists of two steps. The step 1 is to only store the sparse tensors and the basis matrices satisfied that fold. Specifically,

where are initialized to empty matrices. It is not difficult to check that the above formulas satisfy the update of . Step 2 is using a trick shown in Algorithm 1 to reduce the size of the basis matrices without considerably increasing the objective function value F(X) when , where is a given threshold. This trick avoids the problem that the basis matrices gradually increase in size and then cause memory-explosion.

We summarize the complete procedure in Algorithm 2. Since the algorithm only accesses the observed entries of S, X and require rank-one SVD operation, it is efficient in terms of both space and time.

C. Analysis of Space-Complexity and Time-Complexity

It is well-known that the complexities of space and time are very important to evaluate one algorithm. In this section, for an Nth-order tensor X with size , we aim to analyze the proposed method in terms of space complexity and time complexity. Seen from the Algorithm 2, all the operations are based on the sparse tensors of observed entries and a set of basis matrices . Thus, the space complexity of the proposed method is per iteration, where . For the time-complexity of the proposed method, the main per-iteration cost

lies in the update of which consist of the rank-one SVDs of for and the computation of Equation (17). The rank-one SVDs performed by the power method require a cost of , and the time-cost of Equation (17) is . Therefore, the overall time-complexity of the proposed method is per iteration.

TABLE I summarizes the space-complexity and time-complexity of other tensor-norm based algorithms: (i) Overlapped nuclear norm HaLTRC [30]; (ii) Overlapped nuclear norm via tensor-train SiLRTC-TT [31]; (iii) Tensor nuclear norm TNN [44]; (iv) Overlapped Tensor-ring nuclear norm TRNNM [32]; (v) Scaled latent nuclear norm FFWTensor [11]. Since HaLTRC and TRNNM impose N auxiliary variables and N Lagrangian multipliers to simplify the optimization, they both require a space-complexity of per iteration. TNN requires two additional variables, and SiLRTCTT has N auxiliary variables. Thus their per-iteration spacecomplexities are and , respectively. Similar to the proposed algorithm, FFWTensor only needs to store the sparse tensors and a set of basis matrices at a cost of per iteration. And the per-iteration time-complexity of these algorithms can be obtained according to the corresponding papers.

Seen from TABLE I, it is not difficult to observe that LTRNNM requires a much smaller space-complexity over the other compared algorithms when the target tensor X has a high missing ratio and . This is because the sparsity structure of X is efficiently used in LTRNNM. When N = 3, LTRNNFW reduces to the unscaled version of FFWTensor, thus they have the same space-complexity. It is worthy noting that LTRNNM requires much lesser storage space over FFWTensor when N > 3, due to is significantly smaller than .

Note that, both LTRNNFW and FFWTensor have the smaller order of magnitude of time-complexity than the other compared algorithms, which is benefit from the sparsity structure of the target tensor and the efficient rank-one SVD used during iterations. In contrast, other algorithms have to operate on the full-sized tensors and perform partial-SVD in each iteration. Typically, performing rank-one SVD is much significantly faster than partial-SVD, especially for the large scale matrix. Therefore, it is not surprising that LTRNNFW and FFWTensor are time-efficient.

TABLE I: Space-Complexity and Time-Complexity of algo- rithms for one iteration.

A. Effect of β for the Proposed Method

This section aims to investigate the effect of the constraint parameter for the proposed method on the synthetic data with the latent structure of . All the are generated such that has a low-rank structure, i.e. , where the values of and are drawn randomly from the standard Gaussian distribution N(0, 1). For simplicity, we set the dimension of each mode same and so does the corresponding low-ranks, i.e., . The uniformly random missing ratio of 50% is considered in this experiment, and the relative squared error (RSE) is used as

Fig. 2: Plots of relative square error versus .

the evaluation index. The RSE between the estimation and the true one X is defined by RSE .

Fig. 2 shows the plots of RSE versus for tensors of different size (4D), (5D), (6D) and corresponding rank tuples (5, 5, 5, 5) (4D), (6, 6, 6, 6, 6) (5D), (7, 7, 7, 7, 7, 7) (6D). The plots illustrate that the proposed method is robust to constraint parameter in a wide range, which is an important property for algorithms in practical applications.

B. Performance in High-Order Form

To the best of our knowledge, reshaping low-order tensors into high-order tensors is a common practice to improve the performance for TT/TR-based methods on visual-data completion [27], [28], [31], [32], [38]. To evaluate the proposed method in high-order form, the first 180 frames of the brain Magnetic Resonance Imaging (MRI) [30] with cropped size is considered in this experiment. Thus, we present the MRI data by the 3rd-order tensor of size and further reshape into tensors of size (6D), (9D) and (12D). RSE, peak signal-to-noise ratio (PSNR), structural similarity (SSIM) [45], storage size during iteration (SSDI) and RunTime are used to evaluate the performance. The PSNR between the estimation and the true one X is defined by PSNR MSE), where MSE num(X) and num(X) denotes the number of entries of X. We choose FFWTensor method to be the baseline, due to it and the proposed method both took full advantage of the sparsity structure of the observed tensor during iterations. For simplicity, the SSDI of both FFWTensor and the proposed method is defined by a sum of the total number of entries of basis matrices and the number of observed entries, i.e., SSDI .

TABLE II shows the performance of FFWTensor and LTRNNFW under different-order form {3D, 6D, 9D, 12D} and missing ratios {70%, 75%, 80%, 85%, 90%, 95%}. Obviously, the proposed method obtains significantly better results in the high-order form {6D, 9D}, while slightly degrades the performance after further reshaping into 12D form. This implies that reshaping low-order tensor to high-order tensor does help to improve the performance, especially when reshaping into an appropriate high-order form. However, FFWTensor achieves the worse performance after reshaping into high-order form. In addition, it can be observe that:

• In 3D case, the proposed method obtains similar results as FFWTensor, which is caused by that the proposed method reduces to the unscaled version of FFWTensor when encountering 3rd-order tensors.

• In high-order cases, i.e. {6D, 9D, 12D}, the proposed method significantly obtains better results over FFWTensor in terms of RSE, PSNR, SSIM, SSDI and RunTime. Note that, the main difference of the proposed method from FFWTensor is a more balanced unfolding scheme applied in the proposed method. Better results of {RSE, PSNR, SSIM} illustrate the powerful ability of the balanced unfolding scheme in catching the global information. Smaller values of SSDI and RunTime imply stronger power of data- representation and more space-and-time efficiency, which is meaningful when encountering large-scale data or the memory is limited. Moreover, as shown in Fig. 3, the recovery frame by the proposed method is more clear than that by FFWTensor. All these results show the superiority of the proposed method in processing the high-order tensors.

C. Visual Data Inpainting

In this section, we compare the proposed method to other state-of-the-art norm-based methods, including HaLRTC [30], SiLRTC-TT [31], TNN [44], TRNNM [32] and FFWTensor [11]. To evaluate these methods, extensive experiments are conducted on three visual-data sets: (i) A hyperspectral image (HSI)1 of size , which records the area of urban landscape; (ii) The Train-video2 which consists of 80 color frames of size , presented by a tensor of size ; (iii) The AT&T ORL3 face data set which consists of 10 different images of size for each of 40 distinct subjects, presented by a tensor of size . Since reshaping the visual data into high-order tensor signifi-cantly improve the performance of the TT/TR-based methods (i.e. proposed method, TRNNM and SiLRTC-TT), which is illustrated in our experiments and previous works [31], [32], we reshape these three visual-data sets into high-order tensors for the TT/TR-based methods. Specifically, the HSI, Trainvideo and AT&T ORL face data are reshaped into high-order tensors of size (6D), (7D) and (7D), respectively. In our experiments, the parameters of the compared methods are set according to the corresponding paper such to achieve the best results.

As shown in Fig. 4, 5, 6, RSE, PSNR, and Runtime are used to evaluate the performance of each method on these three visual-data sets under uniformly random missing ratios {80%, 85%, 90%, 95%}. Observe that, in our considering cases, the proposed method outperforms the other methods at a small time-cost. Better results of RSE and PSNR are benefited from

Remote Sensing Scenes 2Available at https://www.youtube.com/watch?v=6mcDsY0TwcA 3Available at http://www.uk.research.att.com/facedatabase.html.

TABLE II: Performance (RSE, PSNR, SSIM, SSDI and RunTime) of FFWTensor and LTRNNFW under different-order form {3D, 6D, 9D, 12D} and missing ratios { 70%, 75%, 80%, 85%, 90%, 95%}.

Fig. 3: The visual results of FFWTensor and LTRNNFW on the MRI images with the uniformly missing ratio of 95%. The recovery results are shown by randomly picking slices.

the powerful ability of a more balanced unfolding scheme in catching the global information. Smaller time-cost is caused by the efficiently-utilization of sparsity structure and rank-one SVD operation during iteration. Though FFWTensor method spends comparable time-cost with the proposed method, it fails to achieve good performance as the proposed method in most cases, especially in high missing-ratio cases {90%, 95%}. The other methods (i.e. HaLRTC, SiLRTC-TT, TNN, TRNNM) can achieve comparable results with the proposed method in some cases, however, require largely time-cost. Moreover, for HaLRTC, SiLRTC-TT, and TRNNM, the computational expensive determination of several weighting-parameters sig-nificantly increase their time-cost. These imply that, compared to the proposed method, other norm-based completion methods are not good choices for the large-scale data in practical applications. In addition, the visual results of each method on these three data sets are shown in Fig. 7, 8, 9. Observe that the proposed method obtains the recovery images with a better resolution and captures much more detailed information, e.g. wheel, beard, and eyes.

In this paper, a new latent nuclear norm equipped with a more balanced unfolding scheme is defined for low-rank regularization, and an efficient Frank-Wolfe algorithm is developed for optimization by utilization of sparsity structure and rank-one SVD operation. We theoretically analyze that the proposed method is much more efficient over other norm-based methods in terms of both time and space, which is important for the memory-limited equipment in practical applications. Furthermore, extensive experimental results confirm that the proposed method can achieve state-of-the-art performance in visual-data inpainting at smaller costs of time and space.

[1] P. M. Geona, M. Baburaj, and S. N. George, “Entropy-based reweighted tensor completion technique for video recovery,” IEEE Transactions on Circuits and Systems for Video Technology, 2019.

[2] Y. Liu, Z. Long, H. Huang, and C. Zhu, “Low cp rank and tucker rank tensor completion for estimating missing components in image data,” IEEE Transactions on Circuits and Systems for Video Technology, 2019.

[3] S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” Inverse Problems, vol. 27, no. 2, p. 025010, 2011.

[4] D. Kressner, M. Steinlechner, and B. Vandereycken, “Low-rank tensor completion by riemannian optimization,” BIT Numerical Mathematics, vol. 54, no. 2, pp. 447–468, 2014.

[5] Y. Pang, X. Li, and Y. Yuan, “Robust tensor analysis with l1-norm,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 2, pp. 172–178, 2009.

[6] Y. Xu, R. Hao, W. Yin, and Z. Su, “Parallel matrix factorization for low-rank tensor completion,” Inverse Problems and Imaging, vol. 9, pp. 601– 624, 1 2015.

[7] B. Romera-Paredes and M. Pontil, “A new convex relaxation for tensor completion,” in Advances in Neural Information Processing Systems, pp. 2967–2975, 2013.

[8] I. Kajo, N. Kamel, and Y. Ruichek, “Incremental tensor-based com- pletion method for detection of stationary foreground objects,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 29, no. 5, pp. 1325–1338, 2018.

[9] Y. Liu, F. Shang, L. Jiao, J. Cheng, and H. Cheng, “Trace norm regularized candecomp/parafac decomposition with missing data,” IEEE transactions on cybernetics, vol. 45, no. 11, pp. 2437–2448, 2014.

[10] R. Jenatton, N. L. Roux, A. Bordes, and G. R. Obozinski, “A latent factor model for highly multi-relational data,” in Advances in Neural Information Processing Systems, pp. 3167–3175, 2012.

[11] X. Guo, Q. Yao, and J. T.-Y. Kwok, “Efficient sparse low-rank tensor completion using the frank-wolfe algorithm,” in Thirty-First AAAI Conference on Artificial Intelligence, 2017.

[12] K. Wimalawarne, M. Sugiyama, and R. Tomioka, “Multitask learning meets tensor factorization: task imputation via convex optimization,” in Advances in neural information processing systems, pp. 2825–2833, 2014.

[13] E. Frolov and I. Oseledets, “Tensor methods and recommender systems,” Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 7, no. 3, p. e1201, 2017.

[14] F. Shang, Y. Liu, J. Cheng, and D. Yan, “Fuzzy double trace norm minimization for recommendation systems,” IEEE Transactions on Fuzzy Systems, vol. 26, no. 4, pp. 2039–2049, 2017.

[15] V. N. Ioannidis, A. S. Zamzam, G. B. Giannakis, and N. D. Sidiropoulos, “Coupled graphs and tensor factorization for recommender systems and community detection,” arXiv preprint arXiv:1809.08353, 2018.

[16] R. Bro, “Multi-way analysis in the food industry-models, algorithms, and applications,” in MRI, EPG and EMA, Proc ICSLP 2000, Citeseer, 1998.

[17] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup, “Scalable tensor factorizations for incomplete data,” Chemometrics and Intelligent Laboratory Systems, vol. 106, no. 1, pp. 41–56, 2011.

[18] L. Sorber, M. Van Barel, and L. De Lathauwer, “Optimization-based algorithms for tensor decompositions: Canonical polyadic decomposition, decomposition in rank-(l r,l r,1) terms, and a new generalization,” SIAM Journal on Optimization, vol. 23, no. 2, pp. 695–720, 2013.

[19] T. Yokota, Q. Zhao, and A. Cichocki, “Smooth parafac decomposition for tensor completion,” IEEE Transactions on Signal Processing, vol. 64, no. 20, pp. 5423–5436, 2016.

[20] Q. Zhao, L. Zhang, and A. Cichocki, “Bayesian cp factorization of incomplete tensors with automatic rank determination,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, pp. 1751–1763, Sept 2015.

[21] Q. Zhao, G. Zhou, L. Zhang, A. Cichocki, and S. I. Amari, “Bayesian robust tensor factorization for incomplete multiway data,” IEEE Transactions on Neural Networks and Learning Systems, vol. 27, pp. 736–748, April 2016.

[22] Y.-L. Chen, C.-T. Hsu, and H.-Y. M. Liao, “Simultaneous tensor de- composition and completion using factor priors,” IEEE transactions on pattern analysis and machine intelligence, vol. 36, no. 3, pp. 577–591, 2013.

[23] Y. Liu, F. Shang, H. Cheng, J. Cheng, and H. Tong, “Factor matrix trace norm minimization for low-rank tensor completion,” in Proceedings of

Fig. 4: Comparison of RSE, PSNR and runtime (seconds) on HSI images under varying missing ratios.

Fig. 5: Comparison of RSE, PSNR and runtime (seconds) on the Train video under varying missing ratios.

Fig. 6: Comparison of RSE, PSNR and runtime (seconds) on AT&T ORL images under varying missing ratios.

the 2014 SIAM International Conference on Data Mining, pp. 866–874, SIAM, 2014.

[24] M. Filipovic and A. Jukic, “Tucker factorization with missing data with application to low-nrank tensor completion. multidim. syst,” Sign. P, 2013.

[25] Y. Liu, F. Shang, W. Fan, J. Cheng, and H. Cheng, “Generalized higher- order orthogonal iteration for tensor decomposition and completion,” in Advances in Neural Information Processing Systems, pp. 1763–1771, 2014.

[26] L. Yuan, Q. Zhao, and J. Cao, “Completion of high order tensor data with missing entries via tensor-train decomposition,” in International Conference on Neural Information Processing, pp. 222–229, Springer, 2017.

[27] L. Yuan, Q. Zhao, and J. Cao, “High-order tensor completion for data recovery via sparse tensor-train optimization,” in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1258–1262, IEEE, 2018.

[28] W. Wang, V. Aggarwal, and S. Aeron, “Efficient low rank tensor

ring completion,” in 2017 IEEE International Conference on Computer Vision (ICCV), pp. 5698–5706, Oct 2017.

[29] L. Yuan, J. Cao, Q. Wu, and Q. Zhao, “Higher-dimension tensor completion via low-rank tensor ring decomposition,” arXiv preprint arXiv:1807.01589, 2018.

[30] J. Liu, P. Musialski, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, pp. 208–220, Jan 2013.

[31] J. A. Bengua, H. N. Phien, H. D. Tuan, and M. N. Do, “Efficient tensor completion for color image and video recovery: Low-rank tensor train,” IEEE Transactions on Image Processing, vol. 26, no. 5, pp. 2466–2479, 2017.

[32] J. Yu, C. Li, Q. Zhao, and G. Zhou, “Tensor-ring nuclear norm minimization and application for visual-data completion,” in ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3142–3146, May 2019.

[33] R. Tomioka and T. Suzuki, “Convex tensor decomposition via struc- tured schatten norm regularization,” in Advances in neural information

Fig. 7: The visual results of each algorithm on the HSI data with the uniformly missing ratio of 95%. The recovery results are shown in RGB format by picking the three bands of 70, 40, 10.

Fig. 8: The visual results of each algorithm on the Train video with the uniformly missing ratio of 80%. One frame of the video is picked to show the recovery results.

Fig. 9: The visual results of each algorithm on the AT&T ORL images with the uniformly missing ratio of 80%. 20 images are picked to show the recovery results.

processing systems, pp. 1331–1339, 2013.

[34] A. Wang, X. Song, X. Wu, Z. Lai, and Z. Jin, “Latent schatten tt norm for tensor completion,” in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2922–2926, IEEE, 2019.

[35] L. Yuan, C. Li, D. Mandic, J. Cao, and Q. Zhao, “Tensor ring decom- position with rank minimization on latent space: An efficient approach for tensor completion,” arXiv preprint arXiv:1809.02288, 2018.

[36] Q. Zhao, G. Zhou, S. Xie, L. Zhang, and A. Cichocki, “Tensor ring decomposition,” CoRR, vol. abs/1606.05535, 2016.

[37] Q. Zhao, M. Sugiyama, L. Yuan, and A. Cichocki, “Learning efficient tensor representations with ring-structured networks,” in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8608–8612, IEEE, 2019.

[38] J. Yu, G. Zhou, Q. Zhao, and K. Xie, “An effective tensor completion method based on multi-linear tensor ring decomposition,” in Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), 2018, pp. 1344–1349, IEEE, 2018.

[39] R. Tomioka, K. Hayashi, and H. Kashima, “Estimation of low-rank tensors via convex optimization,” arXiv preprint arXiv:1010.0789, 2010.

[40] C. Lu, J. Feng, W. Liu, Z. Lin, S. Yan, et al., “Tensor robust principal component analysis with a new tensor nuclear norm,” IEEE transactions on pattern analysis and machine intelligence, 2019.

[41] M. Frank and P. Wolfe, “An algorithm for quadratic programming,” Naval research logistics quarterly, vol. 3, no. 1-2, pp. 95–110, 1956.

[42] M. Jaggi, “Revisiting frank-wolfe: Projection-free sparse convex opti- mization.,” in ICML (1), pp. 427–435, 2013.

[43] N. Halko, P.-G. Martinsson, and J. A. Tropp, “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,” SIAM review, vol. 53, no. 2, pp. 217–288, 2011.

[44] Z. Zhang, G. Ely, S. Aeron, N. Hao, and M. Kilmer, “Novel methods for multilinear data completion and de-noising based on tensor-svd,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3842–3849, 2014.

[45] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE transactions on image processing, vol. 13, no. 4, pp. 600–612, 2004.