Sparse and Low-Rank Tensor Decomposition
Motivated by the problem of robust factorization of a low-rank tensor, we study the question of sparse and low-rank tensor decomposition. We present an efficient computational algorithm that modifies Leurgans' algoirthm for tensor factorization. Our method relies on a reduction of the problem to sparse and low-rank matrix decomposition via the notion of tensor contraction. We use well-understood convex techniques for solving the reduced matrix sub-problem which then allows us to perform the full decomposition of the tensor. We delineate situations where the problem is recoverable and provide theoretical guarantees for our algorithm. We validate our algorithm with numerical experiments.
In this submission, the authors propose to solve a tensor factorisation problem of the form Z=X+Y, where X is a low-rank representation of Z and Y represents the sparse corruption. The authors define two subspaces of matrices T_{U,V} and T_{V,W} for a third-order non-symmetric tensor that describe the span of tensor after contraction along either the 1st or 3d mode, respectively. The sparsity after contraction along mode m is characterised by the union of support sets of each matrix (tensor slice) extracted along this mode. Therefore, the authors define incoherence parameters based on L_{inf} norms to control the sparsity, e.g. make spectra of matrices 'diffuse' rather than sparse. The authors employ an extension of the simultaneous diagonalisation [18] by contracting a tensor along modes 1 and 3 by vectors a and b randomly chosen for uniformly distributed unit sphere. This allows obtaining a set of eigenvalues u and v, and v' and w. After pairing eigenvalues u, v, and w, a set of equation arises in which the authors can solve for eigenvectors. For simultaneously imposing low-rank X and sparse Y, the authors apply the simultaneous diagonalisation on contractions of X and Y, respectively, and impose the nuclear norm on all X and \ell_1 norm on all Y, and solve equation 6. This particular subproblem is well explained in [10], e.g. equation 1.3.For evaluations, the authors generate 50^3 dimensional non-symmetric tensors Z composed from low rank X and sparse Y according to distributions described in the paper. The authors present the likelihood of recovery of tensors X and Y from Z w.r.t sparsity and true tensor rank r.  Pros: - an interesting non-symmetric tensor factorisation/decomposition problem - interesting expansion of existing symultaneous positive-definite matrix diagonalisation problem [18]. - interesting way of imposing the low-rank and sparsity related constraints on contractions extending problem [10]Cons: - this submission would benefit from more evaluations, e.g. beyond figure 1 - the last steps of the algorithm in section 2 could be described better - the proofs feel a little bit hard to follow. Major comments: 1. This is a very interesting paper that extends several ideas verging from simultaneous diagonalisation for a set of matrices to low-rank and sparse matrix recovery by applying/extending these methods to third order non-symmetric tensors. The maths behind these methods seems convincing.2. The symultaneous diagonalisation in [18] identifies the problem with using merely one projection vector (equvalent of one contraction). The authors of [18] note in section 3 that the quality of estimated eigenvalues depends on the value of the smallest eigengap. Hence, the authors of [18] propose random projections in order to minimise the situations where a single projection could lead to zeroing some eigenvalues. Do authors of this submission perform multiple contractions? It feels so however it is still very unclear form section 2 or algorithm 1. How does this affect the stability of diagonalisaton given non-symmetric tensors require solving for three sets of eigenvectors?3. The evaluations of the proposed algorithm feel somewhat limited. It'd be very convincing to see an experiment on non-synthetic data. Also, some of the guaranteesgiven in section 3 could be also illustrated in the experimental setting. For instance, what happens in practical simulations when v_3 and v_1 are outside of the guaranteed regime from corollary 3.4?This paper should be interesting to the community researching higher-order tensors. It is sufficiently clear and original despite it relies heavily on prior developments.