Low-Rank Tucker Decomposition of Large Tensors Using TensorSketch
We propose two randomized algorithms for low-rank Tucker decomposition of tensors. The algorithms, which incorporate sketching, only require a single pass of the input tensor and can handle tensors whose elements are streamed in any order. To the best of our knowledge, ours are the only algorithms which can do this. We test our algorithms on sparse synthetic data and compare them to multiple other methods. We also apply one of our algorithms to a real dense 38 GB tensor representing a video and use the resulting decomposition to correctly classify frames containing disturbances.
• We propose an idea for defining the sketch operators upfront. In addition to increasing accuracy and reducing run time, it allows us to make several other improvements. These include only requiring a single pass of the data, and being able to handle tensors whose elements are streamed. To the best of our knowledge, ours are the only algorithms which can do this.
In this paper, the authors present two variants of a random projection-based algorithm (TensorSketch) whose purpose is to obtain a low-rank Tucker approximation for a given multidimensional dataset. It includes the possibility that entries of the data tensor are being streamed in one specific mode. I found the topic interesting and relevant to NIPS because this kind of approach is very important for developing real world big data applications with multidimensional datasets.  However, I found the paper not well structured and lacking of clarity in the presentation among other issues. The authors recognized these issues in their response, found my comments useful to improve the quality of the paper and said they will incorporate changes in the final version. However, there is not detailed information about how the issues will be solved. The main issues I found are the following: - An introduction to “random sketching” is missing. The authors start using the term in the introduction but the it is not explained throughout the paper. They just limited themselves to give references to previous papers. Authors said, they don't want to repeat work from others. - Section 1.2 "A brief introduction to TensorSketch" is very confusing. The authors refer to previous papers where this technique was proposed but it is not explained so the reader gets lost without reading previous works. There are additional information about TensorSketch in the Supplementary information but I found it not useful and very disconnected from the main text of the article. - The usage of matrix B in lines 73 – 76 is misleading. I think there is a mistake and it should be replaced by A in lines 73 and 76. - In line 61, the method COUNTSKETCH is introduced but never explained which makes difficult to follow the article. - Equation (2) is not well motivated and its introduction in section 1.2 is confusing. There is some information about this formula in the Supplemental info but there is no link in the main text to the explanations. Moreover, the operator S^{(n)} is not defined in section 1.2. - First part of section 3, lines 113 – 122, including the classical algorithm HOOI (Algorithm 1: Tucker ALS) should be moved to the introduction section 1.1.  - Section 3.1 (Tucker-TS) is not clearly described. For example, why two operators S_1 and S_2 are needed? How dimension J1 and J2 are chosen? - Authors say that, TensorSketch algorithm meet a theoretical condition of [10] but it is not explained here. Also, they say that avoiding defining a new sketch at every iteration showed better performance in the experiments (Fig. 1) but they were not able to explain this behavior or give some interpretation of this result. - Propositions 3.1 and 3.3 are difficult to interpret without some additional explanations - In Algorithm 2:  Why two parameters J1 and J2 are needed? How these parameters are chosen in practice? Authors propose to have J1=K*R^(N-1) and J2=K*R^N as a practical choice, however it is not clear how to select an optimal value of parameter K.   Only sizes of operators T^(n) are defined in line 2 but how these matrices are generated? Are they Gaussian i.i.d matrices? This should be clearly presented and justified. These questions were not addressed by the authors in their responses. - Algorithm of section 3.2 is not well motivated. Why is this algorithm proposed?  - In the Complexity analysis, the proposed algorithms are compared only to the classical Tucker-ALS algorithm. I think they should compare also to other algorithms such as the ones used in the Experiments. For example, FSTD1 algorithm paper provided a detailed analysis of the complexity. - Figs. 2-3, 4-5 show comparison with other algorithms for sparse tensors. The results of FSTD1 and MACH show relative errors very close to 1 (100%), which, as I understand correspond to totally wrong approximations. The authors justify the poor performance of FSTD1 algorithm because of the sparsity of the tensor. I think this comparison are not useful because FSTD1 is not well defined for sparse tensors. I think comparison of algorithms should be performed also on dense tensors, as the one included in section 4.2. - In section 4.2, it would be worth to show also results applying other algorithms to this dense dataset. - Supplemental material is a set of disconnected sections without no reference in the main text.