Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper establishes a uniform concentration inequality for Kronecker-structured random rank-1 tensors, with a focus on the embedding dimension $m$. The authors consider two random tensor models and characterize the dependence of $m$ on the complexity of the signal $\gamma$ as well as the order $d$. In order to improve its dependence on $d$,  a recursive embedding is further proposed. Finally, the authors apply the general tool to two concrete applications to illustrate its effectiveness.
strengths_and_weaknesses: Strength:
Overall, the paper is well-written and easy to read. The results are interesting and novel, which would certainly contribute to the field.

Weakness:
1. The paper seems to be incomplete --- theoretical guarantees for the tensor decomposition problem in Section 6.2 is missing, and so does the conventional discussion and future direction section.
2. The discussion on the tightness seems insufficient, and part of it relies on a special case. It would improve the quality of the paper to establish the lower bounds for more general cases.
3. For the two applications considered in Section 6, it would be better to compare the results with existing works so as to show the advantage of the general tool developed in this paper.
questions: 1. It would make the paper more accessible to readers if the authors can summarize the notations in an individual section. For example, the authors should provide the definitions of Hadamard product and the transposed Khatri-Rao product in Definition 1.

2. In Definition 2, it seems that $\sigma^2$ is missing in (1) and that there is an extra square root in (2)?
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper analyzes a class of sketchings that write as tensor products of vectors (i.e. random rank one tensor or Kronecker product of vectors if flattened). We know that the sketching discussed here can be calculated for a considerably lower computational cost as a non-structured sketching (to recover unstructured signal). The paper proves that the sketch (also referred to as random embedding) has statistical properties that can be written using properties of each individual signal component (Gaussian width of each of the Cones T1, ... Td): this a strong result because it is not a function of the joint variable (i.e. cartesian product T1 x T2 x .. x Td): this makes it considerably easier to get estimate bounds for the jointly structured sketches. 
The paper discusses (Section 4) a class of random sketches which can be modeled as multi-scale embeddings. It is proven that the minimum embedding dimension m required scales at least exponentially with the tensor order / degree d.
The paper then analyzes a recursive embedding scheme in Section 5 where the paper's Th. 3 result interestingly drops the dependence on the degree (or order of Tensor) d to a polynomial factor. 
The paper provides two applications / examples of Signal Recovery and Optimization problems that highlight the power of their results. 
strengths_and_weaknesses: Strengths: The paper proves that the sketch has statistical properties that can be written using properties of each individual signal component (Gaussian width of each of the Cones T1, ... Td): this a strong result because it is not a function of the joint variable (i.e. cartesian product T1 x T2 x .. x Td). 
The paper's Th. 3 result is very interesting in that it drops the dependence on the degree (or order of Tensor) d to a polynomial factor: there is a statistical and computational reduction in using tensor structured sketches provided that the signal contains this structure. This is a strong result. 
The paper does a good job citing recent papers that have established analogous results in related problems. The paper's Applications examples in Section 6 are concise and convincing. 

Weaknesses: I am not able to flag any technical weaknesses in the paper. 
The paper's presentation is a bit rough. It can take time to the reader to find definitions of the objects introduced (sometimes they're defined a few lines before or after or in cited papers). Example: Definition 1 introduces lots of objects including P_i's that are not defined. I guess they contain a single 1 at one row. Other example: Eq. (2) requires some parsing to figure out what is randomized (it's v's) and epsilon pops out of nowhere. Another notation choice that bothered me is the use of the same letter "a" for  a vector and a tensor at lines 113 & 114. 
questions: is the Th. 3 result tight? the dependence in d, despite being poly, still feels a bit strong to me. Do you have any numerical experiment that at least suggest that the bound is tight? or do you have intuitions why it can be improved? 
limitations: Examples in Section 6 are great, but I suspect that a more elaborate discussion on applications could improve the paper's impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the concentration inequality for random tensor acting on rank-1 Kronecker structured signals and derives a similar near isometric properties for Kronecker structured random tensor embeddings. Two applications related to compressive sensing and tensor decomposition are analyzed. The proposed theory is tested in numerical experiments. The paper is well organized and written clearly. 
strengths_and_weaknesses: *Strengths*
1. Derive a generalization of the Restricted Isometry Property (RIP) to higher-order tensored signals. Also, the proposed Kronecker structured random tensor embeddings allow for efficient implementations (e.g., recursive Kronecker embedding). 
2. The paper is well organized and written clearly.
3. The potential applications are interesting, for example, the compressive sensing of tensor structured signal and tensor decomposition problems.

*Weaknesses*
1. The major contribution of this work is not clear. The main idea of generalizing of the RIP to Kronecker structures has already been extensively explored in the literature. For example, in [1], the authors introduced a generalization of the fast Johnson-Lindenstrauss projection for embedding vectors with Kronecker product structure, the Kronecker fast JohnsonLindenstrauss transform (KFJLT), which is essentially the same topic considered in this work. The reviewer is not clear what's the main innovation compared with the prior works.

[1] Jin, Ruhui, Tamara G. Kolda, and Rachel Ward. "Faster johnson–lindenstrauss transforms via Kronecker products." Information and Inference: A Journal of the IMA 10.4 (2021): 1533-1562.

2. The proposed applications are interesting, but have some practical issues. More precisely, the authors show that under some assumptions the global optimal solution coincides with the ground truth. However, the underlying optimization problems of both applications are essentially nonconvex due to the multi-linear structures. Unlike traditional compressive sensing, the underlying optimization problem is convex, where the global optimal solution is possible/easy to achieve. Due to the nonconvexity, it is not that meaningful to study the properties of its global optimal solutions.

3. The experimental evaluation of the proposed methods is limited.
questions: 1. The reviewer is not clear what's the main innovation compared with the prior work [1]. This is the major question of the reviewer.
[1] Jin, Ruhui, Tamara G. Kolda, and Rachel Ward. "Faster johnson–lindenstrauss transforms via Kronecker products." Information and Inference: A Journal of the IMA 10.4 (2021): 1533-1562.

2. Due to the nonconvexity nature of the Kronecker structures, what other potential applications instead of those inverse problems discussed in the paper?
limitations: 1. The major contribution of this work is not clear. The main idea of generalizing of the RIP to Kronecker structures has already been extensively explored in the literature. For example, in [1], the authors introduced a generalization of the fast Johnson-Lindenstrauss projection for embedding vectors with Kronecker product structure, the Kronecker fast JohnsonLindenstrauss transform (KFJLT), which is essentially the same topic considered in this work. The reviewer is not clear what's the main innovation compared with the prior works.

2. The proposed applications are interesting, but have some practical issues. Due to the nonconvexity, it is not that meaningful to study the properties of its global optimal solutions.

3. The experimental evaluation of the proposed methods is limited.
review_title: null

Meta-review: metareview: The paper derives uniform concentration inequalities for random tensors acting on rank-1, in the spirit of Gordon's inequality. 
This type of results is at the root of a large literature based on the Convex Min-Max theorem which recently allowed for the analysis of plethora of empirical risk minimization problems in convex settings. The paper goes in the direction of providing the necessary tools to go beyond matrices and extend to projections of low rank signals on random tensors. Therefore such results have a very high potential in terms of applicability and is highly relevant to the ML community.
The reviewers are all favorable and I agree with them on the quality of the paper and its presentation. I also acknowledge the detailed answers provided during the rebuttal period. I'm confident that the authors will implement the relevant suggestions of the reviewers to fine tune the final version of the paper.
confidence: Certain
Decision: Accept