Generalized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion
Low-rank tensor estimation has been frequently applied in many real-world problems. Despite successful applications, existing Schatten 1-norm minimization (SNM) methods may become very slow or even not applicable for large-scale problems. To address this difficulty, we therefore propose an efficient and scalable core tensor Schatten 1-norm minimization method for simultaneous tensor decomposition and completion, with a much lower computational complexity. We first induce the equivalence relation of Schatten 1-norm of a low-rank tensor and its core tensor. Then the Schatten 1-norm of the core tensor is used to replace that of the whole tensor, which leads to a much smaller-scale matrix SNM problem. Finally, an efficient algorithm with a rank-increasing scheme is developed to solve the proposed problem with a convergence guarantee. Extensive experimental results show that our method is usually more accurate than the state-of-the-art methods, and is orders of magnitude faster.
Summary: this paper presents a method to decompose and complete tensors. The main idea is to represent the tensor as a product of a low-rank core tensor and a set of orthonormal matrices, and then to minimise the nuclear norm of the core tensor (that is, the sum of the nuclear norms of its unfoldings). Intuitively the algorithm mixes fixed rank decomposition (using an upper bound on the rank) with norm-regularisation. The approach is analysed theoretically (in terms of convergence & recovery) and empirically (on one synthetic dataset and one real-world dataset). Quality: This is a nice idea, and I think it has been executed well. The optimisation is non-trivial and comes with some guarantees, and the scalability of the algorithm is convincing. Results suggest good performance on the chosen dataset compared to a set of state-of-the-art methods. There are some things that concern me. First, I find the empirical comparison relatively weak as only a single dataset was considered, and this dataset seem to have been used in other tensor factorisation papers (authors, please clarify if this is not the case and the data has indeed been used before). Why not use datasets from other papers, such as the network traffic data of Acar et al, or the Ocean video of Liu et al? Second, I find the stability guarantees not very convincing. It is true that the middle term in equation 21 diminishes with increasing sample size and hence the impact of the constant C, but without any bounds on C to me this theorem does provide much practical use (that said, Wang & Xu give the same type of guarantee). However, I find the method useful enough to not count this against the paper, it’s an add-on to me. Question: I am a little surprised that your method is faster than the WTucker method, as my impression is that your essentially solve something like a Tucker decomposition in your inner loop (when estimating your U and G matrices/tensors). Am I missing something?  Clarity: Generally I found this paper to be quite well written. However, I think the description of the algorithm could be slightly improved by making it the currently used set of ranks more explicit. The algorithm is maintaining one rank per mode, which is increased over time (to always reach the R_i, … R_N ranks). If you mention this before equation 9, and that the current ranks are used in this equation (not the R_i chosen in advance), it would be much clearer to me. Second, it would be helpful to discuss briefly implications (and interpretations) of section 4. For example, why could Theorem 4 be helpful even though you have no bound on C?  Originality: I find the main idea relatively original. It brings together a few ideas in a novel way (norm of core tensor = norm of full tensor, ADMM, HOOI, stability analysis a la Wang & Xu). It’s still not gonna change the way of thinking of the field.  Significance: While the method itself isn’t ground breaking, the outcome of increased scalability w/ less sensitivity to rank estimation is quite significant. This could certainly be a method I’d be eager to try (although I’d still like to see more empirical evidence that this works).