Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
We consider the problem of recovering a low-rank tensor from its noisy observation. Previous work has shown a recovery guarantee with signal to noise ratio O(n K/2 /2 ) for recovering a Kth order rank one tensor of size n × · · · × n by recursive unfolding. In this paper, we first improve this bound to O(n K/4 ) by a much simpler approach, but with a more careful analysis. Then we propose a new norm called the subspace norm, which is based on the Kronecker products of factors obtained by the proposed simple estimator. The imposed Kronecker structure allows us to show a nearly ideal O( √ n + √ H K−1 ) bound, in which the parameter H controls the blend from the non-convex estimator to mode-wise nuclear norm minimization. Furthermore, we empirically demonstrate that the subspace norm achieves the nearly ideal denoising performance even with H = O(1).
This paper introduces a new theoretical bound for recovering a low-rank tensor from a noisy observation as well as a new norm on tensors.Among the neatest results in this paper is a demonstration and a proof that there is a two-phased behavior of the recovery.There are a number of problems with the paper, but quality, clarity and significance are my main concerns.The papers quality suffers mainly due to poor grammar, poor terminology, notation and terms that aren't properly and clearly defined.It is unclear how significant any of the results are as the authors have not demonstrated a meaningful improvement in a practical setting.The sub-space norm for example improves things when the relative error is close to 1, but why do I care what happens in a situation where the model is anyways useless?I would have expected a discussion on the practical value of the result - especially given that the signal to noise ration required is quite large (even if reduced dramatically from earlier papers).I can only presume that a lack of such a discussion means the value is marginal and that this should be seen as mainly a theoretical contribution?Here are some comments"Tensor is a natural way" --> "The tensor is a natural way" "for variety of data" --> "for a variety of data" "ranging from ..., neuroimaging" --> "ranging FROM ... TO neuroimaging" what is model 2 in the comment of table 1? "(Vershynin, 2010)" --> this should be a proper reference.This is one of many demonstrations that the paper was not really completed. "mn" vs "nm" : Just be consistent with the order of the product so as not to distract the reader with irrelevant details.Definition (4) is completely bogus.You can't redefine "k-1, ..., k+1" to mean "1,...,k-1,k+1,...,K".Also, you only sometimes use this definition.Even the right hand of (4) is written in a terrible way.In stead of writingA^{(k-1)}\otimes \cdots \otimes A^{(1)} \otimes A^{(K)} \otimes \cdots \otimes A^{(k+1)} I would prefer A^{(1)}\otimes \cdots \otimes A^{(k-1)} \otimes A^{(k+1)} \otimes \cdots \otimes A^{(K)} which clearly shows that the term A^{(k)} is the one left out.Even clearer and more succinct would be \otimes_{i\neq k} A^{(i)}"n_1\times \cdots n_K" should be "n_1\times \cdots \times n_K".This sort of mistake is made repeatedly in the paper.M is not properly defined.I would in the least expect to see the sizes of M defined. Is there a missing sum in the definition of Z_{(k)}^{(k)}?If not then you may as well say that Z has a rank one factorization as opposed to a low-rank factorization?In any case things it's not exactly clear to me what exactly Z is."r=1,\ldots R" --> "r=1,\ldots,R"All the graphs are too busy (and extremely small) to make sense of.  The experiments use a cheating type of method to find lambda, and the rank is assumed known.I assume that in reality both lambda and the rank will be unknown.The only real data experiment was the amino acids data example.It's unclear that the paper added any practical value to analyzing these sort of data sets.