Convex Tensor Decomposition via Structured Schatten Norm Regularization
We study a new class of structured Schatten norms for tensors that includes two recently proposed norms ("overlapped" and "latent") for convex-optimizationbased tensor decomposition. We analyze the performance of "latent" approach for tensor decomposition, which was empirically found to perform better than the "overlapped" approach in some settings. We show theoretically that this is indeed the case. In particular, when the unknown true tensor is low-rank in a specific unknown mode, this approach performs as well as knowing the mode with the smallest rank. Along the way, we show a novel duality result for structured Schatten norms, which is also interesting in the general context of structured sparsity. We confirm through numerical simulations that our theory can precisely predict the scaling behaviour of the mean squared error.
****Additional comments after the rebuttal: The 
      authors need to do a much better job on motivating the problem for machine 
      learning, for the paper to be accessible to a wider audience. The authors 
      need to provide the latent variable model (with a graphical model 
      representation) where this tensor decomposition can learn the parameters: 
      Consider a model where latent variable h_1 connects to observed variable 
      x_1, h_2 to x_2 and so on. Assume a linear model from hidden to observed 
      variables, and arbitrary dependence among the h_i's. In this case, the 
      observed moment tensor has a tucker decomposition and its multilinear rank 
      is dim(h_1), dim(h_2).. The authors need to add this discussion and 
      preferably provide a picture depicting this model. The authors also need 
      to point out that it is possible that only some hidden variables are of 
      small dimensions and not the others, which was a main advantage for the 
      new result in the paper. The paper considers convex-optimization 
      based tensor decomposition using structured Schatten norms for tensors. 
      The authors employ the overlapped Schatten norm and show how it leads to 
      better reconstruction guarantees. The paper is well written and makes 
      technically important contributions. Fixing a few technical and notational 
      issues, will make the paper even more readable. *Clarification 
      about Theorem 2 and its proof: Statement of theorem 2 is 
      technically not correct: the components are only recovered up to a 
      permutation. Although a minor issue, the authors need to mention this. 
      In Theorem 2, it is stated that (12) immediately leads to (13). 
      This needs a justification. Proof of Lemma 5 is missing. Lemma 5 
      forms a key part of Theorem 2. It is better to clarify the proof 
      of Lemma 4 explicitly rather than referring to another paper, although it 
      is straightforward. *Minor issues: Need to add more 
      related work on HOSVD and other methods for tensor decomposition: The 
      authors can mention how the higher order SVD and its variants yields 
      approximation bounds for tensor decomposition. See Kolda's review on 
      tensor decompositions (section 4). The notion of rank that the 
      authors use, which they refer to as mode-rank is also referred ot as 
      multilinear rank. The authors can mention this and note there are 
      different notions of tensor rank in the introduction. The authors 
      can briefly discuss the computational complexity of the methods employed. 
      The authors need to clarify their discussion about incoherence 
      after (10). The authors use the term to mean that they need the "energy" 
      to be spread across different mixture components and modes, i.e., no 
      component or mode can have too high a singular value. The authors mention 
      that this is the same as the incoherence conditions of [1,3,10]. I do not 
      see this. In [1,3,10], incoherence notions are use for sparse+low rank 
      recovery. However, here, the noise is not sparse. The condition of 
      [1,3,10] involves the singular vectors being incoherent with the basis 
      vectors. This is different from the condition here. Suggest removing this 
      comparison. *Typos/notational issues: Superscript notation 
      for components \hat{\cal{W}}^{(k)} is confusing. Suggest using some other 
      symbol for components. Bad notation: \bar{r}_k and \underline{r}_k 
      are both used for k-mode rank. This should be changed. Could introduce 
      mult_rank(tensor) instead to denote the multilinear rank. In Last 
      line of page 12 in supplementary material, some parenthesis is missing. 
      Abstract: "result for structures Schatten" should change to 
      structured