A New Convex Relaxation for Tensor Completion
We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable.
**** Updated after authors' feedback **** My main 
      concerns are still that - the improvement compared to L1 (or trace 
      norm) comes from the discontinuousness at the boundary of the domain, 
      where the solution almost never lies (as the authors point out). - on 
      the other hand, probably the proposed regularizer agrees with the L1 if 
      ||w||_1 ≤ alpha, because it agrees with L1 on all the points on the L2 
      ball that have cardinality one, and the convex envelope of those points 
      defines the ball ||w||_1 ≤ alpha. 
      ***************************************** This paper 
      proposes a new convex relaxation of the tensor multi-linear rank based on 
      the convex envelope of the cardinality function intersected with an 
      L2-norm ball of some radius alpha. The proposed convex relaxation 
      is in the line of previous studies [7,15,19,20,22] that studied trace norm 
      of the unfoldings (matricizations) of a tensor along different modes. The 
      current paper points out that the tensor trace norm used in previous 
      studies is not the tightest convex relaxation with respect to the 
      Frobenius norm (L2 norm of the spectrum). To fix this, the authors apply 
      the convex envelope of the cardinality function intersected with an 
      L2-norm ball to the spectra of the unfoldings of a given tensor. 
      The authors show that the proposed convex envelope (for 
      cardinality) is tight for any vector having the prespecified radius alpha. 
      The trace norm is the tightest convex relaxation of the rank in terms of 
      the spectral norm. The authors argue however that the spectral norm is not 
      invariant to the choice of the mode to unfold a given tensor, nor is the 
      tightness of trace norm. On the other hand, the Frobenius norm is 
      invariant, so is the tightness of the proposed convex relaxation. 
      Some numerical experiments show that the proposed convex 
      relaxation outperforms tensor trace norm in tensor completion. 
      Strength: - The proposed convex relaxation is new and it seems 
      to work. - The idea might be used for inducing sparsity in general. 
      Weakness: - The result of Lemma 1 seems applicable to other 
      sprasity problems (sparsity, group sparsity, low-rank matrices). The 
      authors should clarify how much of the contribution is specific to 
      low-rank tensors. - The authors do not prove that the proposed 
      regularizer is the tightest convex relaxation for the combinatorial 
      regularizer Omega(W) (they only show the tightness of the convex envelope 
      function used to construct the regularizer in Lemma 1 and it is *tighter* 
      than the trace norm in Prop 2). - The proposed convex relaxation seems 
      rather hard to compute. It is infinity for ||x|| > alpha and it has 
      many discontinuities for ||x||=alpha. This probably makes the optimization 
      and also proving something about the estimator hard. - It would be 
      nice if the authors could discuss any connection between this work and the 
      k-support norm proposed in Argyriou et al. NIPS 2012) Minor 
      comments: - The statement "if F_alpha(W) ≤ Omega(W) for every W\in G_2 
      then F_alpha(W) ≤ Omega(W) for every G_infty." (line 138) seems false, 
      because G_2 is a smaller set than G_infty. - The choice of alpha as in 
      line 321 may not be the best, because the proposed regularizer is infinity 
      for ||W||_F > alpha. It should be chosen more carefully. - It was 
      not clear how tight the proposed regularizer is when ||W||_F < alpha. I 
      guess it equals the trace norm when ||W||_tr ≤ alpha (Correct me if I am 
      wrong). - What kind of performance guarantee can you prove for this 
      regularizer? How does that compare to Tomioka et al. "Statistical 
      Performance of Convex Tensor Decomposition" (NIPS 
      2011)?