Near-Isometric Properties of Kronecker-Structured Random Tensor Embeddings
Authors: Qijia Jiang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Structured non-symmetric rank-1 tensor
Uniform deviation bound
Applications of random tensor embeddings

Abstract: We give uniform concentration inequality for random tensors acting on rank-1 Kronecker structured signals, which parallels a Gordon-type inequality for this class of tensor structured data. Two variants of the random embedding are considered, where the embedding dimension depends on explicit quantities characterizing the complexity of the signal. As applications of the tools developed herein, we illustrate with examples from signal recovery and optimization.

Near-Isometric Properties of Kronecker-Structuree Random Tensor Embeddings
Qijia Jiang
Lawrence Berkeley National Laboratory qj gjiang01bl.gov
Abstract
We give uniform concentration inequality for random tensors acting on rank- I Kronecker structured signals, which parallels a Gordon-type inequality for this class of tensor structured data. Two variants of the random embedding are considered, where the embedding dimension depends on explicit quantities characterizing the complexity of the signal. As applications of the tools developed herein, we illustrate with examples from signal recovery and optimization.
Introduction
It is hardly an overstatement to proclaim that underpins most of the analysis for high- nigh-dimensional statistics and structured signal recovery the heavy hammer made possible by the machinery of Gaussian process, and in particular Gordon-type inequality that gives tight characterization of the suprema of the empirical process with geometrie properties of the underlying index set. this paper, put poonecker-structuree random tensors into scrutiny and ask for analog of Gordon's 's incquality for correspondingly censor-structured signals. We embark with a brief reminder of the classics.
1.1
Gordon's inequality for Gaussian random matrix
For signal u E T CR" a vector, it is known for S E R random i.i.d standard Gaussian matrix,
E[min [[Su]]] 2 am wT() and E[max ||Su]]] um + w(T) uET
wel
for Um = B for set 7 C -r comparison lemma (i.e., Pemique-Slepian theorem), which implies for g, independent standard Gaussian vectors,
y where 9m NO0, I..) and ((T) E[maxxeT y ai] the Gaussian width a subset of the unit sphere. This statement hinges on the Gaussian min-max
Eg min max g T h Es mmn max T Su]. WET vES
(1)
WET VES
This trades the quadratic form for more innocuous separable process, from which one can see that the LHS evaluates to the first part of the previous display. The other side is essentially sim- ilar. For this expectation bound to justify the attention it deserves, one needs to recognize that minger [/Sull (analogously for max) is a Lipschitz function in the Gaussian random matrix S, from which (dimension- free)) concentration inequality, alongside the bound on the expectation derived above, conspire to deliver a uniform concentration bound as stated below.
Theorem (Gordon's 's escape through the mesh
(12). For all T C. R", where T is a (not necessarily convex) cone, with probability at least exxp(- 52 for S entrywise i.dd standard Gaussian,
1 - [--)|lu|| S am
||Su||| s (1 |u|
when m. > +6)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Later work of CGMT 17 showed that the reduction of ① is essentially tight for convex sets, which has surprising consequences for analyzing the risk of various statistical estimators in high- dimensional asymptotic regime. This elegant analysis, nevertheless, cannot be carried out beyond (even for subgaussian), but gives that for example, the extreme singular values of a Gaussian random matrix 1/ /mm S scales as 1 + vn/m by picking T = gn-1 It also recovers the familiar LiiinssonLnnddssrruuss lemma for distance-prees prreeerringgi random projection of finite point set when we (log([T]), where [T] the cardinality of the set.
the Gaussian case due to the lack of comparison lemma ①
Seemingly a natural obsession for probabilists for its mathematical allure, results of this flavor have found unexpectedly number of applications across many areas in numerical linear algebra, signal processing, theoretical computer science, among others. Such uniform convergence result is frequently encountered for deriving tight sample complexity bounds for recovery problems, where the problem boils down to characterizing the probability that a random subspace (i.e., null space of Gaussian measurement matrix) distributed uniformly misses the tangent cone of regularizer. Nonconvex gradient- based optimization heavily leans on these tools for characterizing restricted singular value for deriving convergence with Empirical Risk Minimization. Sketching- baased least-squares optimization min, ||SArz Sb1l2 also crucially rely on such results, where w(U n (1="")) = /dim(U) for U colspan([A b)) for the subspace embedding property.
1.2
Contributions
We aim to generalize Gordon's 's uniform concentration result for tensor-structured signal x = u @ @ nd while insisting on efficient computation of the embedding operation. More concretely, we consider Kronecker-structured random rank-1 1 tensor, which when acting on rank-1 tensor-structured signals, can be performed without explicitly forming the bector-y--factor effortlessly. Formally we set out our roadmap to address the following questions:
.... n tensor since it can be done
1. For (1) structured and fast tensored embedding (e.g., (ensor-SRHT as defined in Definition | below); and (2) Sensor-Subgausssan introduced in Definition 2 what is dictated from the embedding dimension m for the following guarantee to hold w.h.p
m 1
||]|| max(e, ||=||3
m
for all x= ===uuo = ud E T x... x (Cartesian product of d not necessarily convex cones), as function of the geometric properties of the individual sets .'.... .7d. is a generalization of the Restricted Isometry Property (RIP) to (I) higher order tensored signals; (2) general cones beyond sparsity. Both sketches above row-wise tensored and take the form S, = vec(w)) @ .... @ o²") for each row E [m]. We are interested in the regime m & nd and instantiate the embedding result for this sketch from Section to bound the restricted singular value as required by tensor signal recovery problem in Section 6.1
This
2. To improve the dependence of yn on the degree d (while maintaining computation efficiency). we consider a recursive embedding in Section 5 which repeatedly calls degree-2 Tensor- SRHT 5 [R as a subroutine as follows: S(u² ( u² ( u²...) = S' (u/ s8 S2 e ( (..)))) ))). Similar uniform concentration is derived on the scaling of m with geometric properties of the individual sets for this alternative embedding, which is in turn called upon to speed up solving for optimization problem in Section 6.2
3. Our technique is based on generic chaining we include comparison with results one would get from more naive method in Section 3 and part with some discussions of lower bound on the embedding dimension in Section and numerical results in Section 7
We pause to emphasize it is the correlation in the tensor structure that introduces difficulty for tight concentration result for general random tensor with i.i.d entries is less challenging to obtain, but at the same time less efficient to apply.
Definition 1 (Tensor-SRHTY, A random matrix constructed as S= J. ..... Patt. Da e
mmmxn is called a Tensor-SRHT (Subsampled Randomized Hadamard Transform), if when acting on a rank-1 degree-d tensor, takes the form S(u² @ .... & ud)) Vm
1 P' H D'vecuu @.... .... @ ud) =

---

H,H, G...OPaH,,, where D' is a x diagonal matrix with entries D1 28.-.00 vin
(i.e., tensor product of independent Rademachers) and P' is a m x n subsampling matrix with a single in each (independent) row and Hn Hn ..... @ Hn where is a power of 2 is the Hadamard matrix of size n' x n. Here @ denotes Hadamard product and o denotes the transposed Khatri-Rao product. Moreover, such embedding can be carried out in time (dd(n log n + m)).
Definition 2 (Tensor-Subgaussinn) We call S E Bmxxn Vensor-Subgaussien embedding if every row S, = vec(o: @ .... & vf)) constructed where each factor is an independent o o-subgaussian isotropic random vector, ie.,, (1) [[(( u2) = 1 13: (2) (2) 12//o/// S /opl w² 1/2 for all 2 2, E [m],j E [d] and any w² E IR".
2 Related Work
In the case of vector-valued signal 1), embedding analysis for infinite sets using structured matrices requires ingenuity and is significantly more involved in general. Notable extensions include ICC. The work of [IS offered a unifying theme- the important message behind is that one can have reduction from RIP based result to Gordon-type inequality by invoking it at different sparsity levels with various distortions à la Talagrand's multi-resolution generic chaining. An orthogonal thread for generalizing to heavier-tail distribution involves small-ball technique which gives an one-sided bound for nonnegative empirical process such undertaking present in e.g., [8].
Previous work on tensor concentration are mostly concerned with operator norm bounds for symmetric subgaussian and/or log-concave (potentially non-isotropic) factors for symmetric forms ||S||op is maximized by a single vector E S therefore for this we only need to content ourselves with a single index set and look moment deviations of type: suPaese-1 E m (S;, u)d (S,, ") an arguably simpler task. Indeed, multi-resolution approach is not strictly beneficial here compared to more elementary arguments (I].
where
The case of non-symmetric factors warrant more care. Both 21 studied pointwise tail bound of the form P[]||xx||2 || 2 t) for S E gmmxn linear mapping, I = u² @ ... @ ud E R²" where 2 are independent factors each with independent, mean O, unit variance, subgaussian coordinates this can in turn be used for deriving a high- probaabibbbby lower bound on miin for the n' m random matrix X where each column is formed by the aforementioned tensor x. Uniform deviation for general sets on tensors can be viewed as a special instance of 2nd-order chaos with mixed tails [66 For example in the case of processes with case when for Tensor-Suie Suuuau--uuaausiian embedding in Definition 2 i.e., Vu > 0,
increments (as is the
P[] X.Il Vuda(1, 8) + udi (1, s)) S 2e"
the result of 9 gave uniform deviation for suPieT |eell as combination of 72( d2) and " di) but crucially these quantities are tied to the metric complexity of the product index set T:= x T something that is hard to compute by and large. Various works also study finite set embedding for Kronecker-structurg sketches, some of which we will leverage for our results and will mention them in later contexts.
3 Discrete JL and Single-scale Approach
At the heart of the following result is a generalized Khinchine inequality 2 which says if (ok axpl)// < Cplla||2 for any vector a E IR" and all independent {o ) then B[] e & od 1/ < C all2 for any (not necessarily rank-1) tensor R= This is closely related to an earlier result from [3] on the concentration of Gaussian chaos but generalized to broader class. Such moment control is only hop away from tail bounds using standard arguments. We establish the finite-set embedding property for the now-wise-tensored embedding matrices below, building upon previous work. This serves as the stepping stone for the embedding of general sets.
Lemma 1 (Discrete- property for Tensor-SRHT and Tensor-Subgaussee
For set of cardinality
p that the rank-1 I tensor x E Ra* belongs, with probability at least e- for any nj > 0 and Tensor-SRHT as defined in Definition 1 satisfies |||S.||| || < max(c,e))]las simultaneously
for all p points provided m e (log (p) + (1 + m)))). The same guarantee holds for
3

---

Tensor-Subgaussian in Definition 2 with m O(C (log"" (p) + (1 + )) for some universal constant C.
Remark. Close inspection of the proof for Theorem 3 in [2] fact uncovers that the discrete JL. property above holds for more general class of SORS (Subsampled Orthogonal Random Sign)
constructions for which H = n J and ma Hyyl S c. In the case d 1, it also recovers lemma.
the classical Johnson-LLindenstrane
Without taking the multi-scale route, in the case d = 1, to guarantee e-distortion over continuous set, one needs to roughly speaking build nene for R" for A S E /mm/n therefore the sample complexity one gets with single-scale approach will scale as
m log (A
mm VTue(T) 2
me4
where we used Sudakov's minorization for bounding the size of the covering with Gaussian width of the set and the JI. Lemma for SRHT/Subgausian matrices for the first transition. This back- on-the-envelope calculation showcases that uniform covering is far from optimal, since in general it could be the case w(T') < /n for T gm subset of the unit sphere and this insight is precisely the reason that motivated [15] to consider a multi-scale approximation that can establish the x w² (T)) guarantee for wider classes of random ensembles beyond the Gaussian case in Theorem I To put things in perspective with later sections, we work out the sample complexity required from naive uniform discretization below.
Lemma 2 (A net Covering). Using Tensor-SRHHE with a uniformly constructed A-net covering of the tensor, requires
22
23 nITa (TT for 2 hold.
Even in the prosaic case of Gaussian process indexed by ellipsoid and/or & ball, it is well-known and disappointing fact that arguments based on union bound Dudley integral don't give the optimal bound, whereas method based on generic chaining does [6]. which we turn to next.
4 A Multi-scale Approach: Row-wise Tensored Embedding
One viable approach is to apply the result of [5 naively to vec(u' 8 u²) without taking into consideration the Kronecker structure, but this is somewhat of futile endeavor if one takes any interest in downstream applications of such bounds. In fact, this was also the impetus for Mendelson's 's work on product empirical processes [1]] it is generally hard to handle geometric properties process indexed by product classes. We will instead derive results with an eye towards bounds involving decoupled geometric complexity measure for each factor that lends itself to explicit computations this necessarily calls for more intricate chaining argument. Another possibility to use a contraction inequality la Ledoux-Talageee bounded class but this will be crude in almost all cases.
if the random factors {ur 1d ر come from
Our agenda is to leverage the results finite set embedding from the previous section, wrap them inside of a chaining argument by exploiting coverings at multiple scales with different dis- tortions/probabiiliyy tradeoff so each level of approximation demands roughly the same embedding dimension (as we will see, the final m depends on the maximum required across all resolutions).
4.1 Preliminaries
Throughout the paper, we use S. to hide absolute constants. To measure the size of the set T C. R". we use Gaussian width defined as for g (n),
w
(T")
E
sup LE
In our context, we define the 72 functional as
DC 25 (T)) inf sup
dist(u' ( Ti)
{If u ET 1=0

---

where the infimum is taken over all sequences of nets (Ti j with cardinality |Ti| < =: Nr vi [d] and T = = =: No. For Gaussian process with canonical metric (i.c., Euclidean norm) on T", the expected supremum is completely characterized by (2"), i.c.
75 (T)) = w(')
where the upper bound is due to Fernique and the (much deeper, bound due to Talagrand's majorizing measure theorem. more general definition working with admissible sequences defines
lower
72 (T = inf sup Σ 2/ diam(()u))) (A)
ET
t=0
where the infimum is taken over all admissible sequences (i.e., increasing sequence partitions of T' with |Ail| I N₁ for all 2 0) and (i denotes the (unique) element of Ai that contains u'. It is not hard to see that by picking one point arbitrarily from each element of the partition, one can build net which implies that always have 72 (T') v 72(T"). In fact, the work of 20 shows that these two quantities are always of the same order.
It is also immediate consequence that for an optimal admissible sequence {Ai picking { as a sequence of nets with cardinally [T & N2 constructed by choosing the center point in every element of the partition set {Ai) we have for all u² E E
2/ dist TT) - inf sup 2 diam (A((t))
(3)
(A;) TETs 1=0
For our results, we will find it helpful to adopt the slightly more general % funncioiolll for a > 0:
dist(ws TT) S (T) = inf sup Σ 2//a 2//a diam(A))))) 1=0
(AH ET
and the infimum is taken over all admissible sequences in exactly the same way as B It is known that for a random variable with tail decay bounded as e- the supremum is upper bounded by the To functional ( Moreover, we always have the following Dudley-style metric entropy integral estimate [6 where By denotes the unit-&z ball in R"
7a (T') S Ca /'' (log N(T',(T. sBB)) 1/a ds,
but the reverse is generally not true. Here the upper limit of the integral goes up to 1 because N WTr, sB3) for by simply picking {0} cover. Covering number on the RHS of 4 can be bounded with estimates on Gaussian width. In particular, Sudakov minorization asserts
sup $V log N(T, <BB) w(T)), #>0
which uses covering number at single scale. Various alternative options exist for upper bounding the covering number, including Volumetric estimates, Maurey's 's empirical method etc.
Estimate f above has the drawback of not being explicit in constants Ca, if one is keen on explicit dependence on a, the following lemma becomes timely.
Lemma (Relationship between Ya functionals). For a S 1, if set T c gn-1 has covering number (TT,, sB²) & ( for some 2
2, then
(T") S Ta (T') < (1 + logg(b/a) (aoloo((a)) 20 r2(TT)
for some absolute constant K.
4.2 Multi-resolution embedding property
Instead of going through the multi-scale RIP (followed by column sign randomization) as done in 15) we will give ourselves more wiggle room by working with a multi-scale embedding property for finite sets. Definition
3 below will be featured prominently in subsequent sections and make the successive construction of approximations less mysterious than it may otherwise seem. We will invoke for Tensor-SRHT and Suugaus-unaa in this section both taking the form where each row S, vec(e) @ ... 2 o.))
5

---

Definition 3 (Multi-resolution Embedding Property). A mapping S "R" + TTT fulfills the (e.7), 0t)- Mulli-resolution Embedding Property if for an increasing sequence of successive coverings {Ti) of T C g"-1 such that (Ti) 22 and (Ti) = Vi E [d] defined in ( for tensor z = u @ ... @ u.
the following holds simultaneously for all 1 S 1 S x [[og2[nd]] with probability at least
1 - exp(-1) -1):
For all E [d] and E [L].
[|| 8 ... 2 ut 8 uf-1) S(uf @ ... 2 ut 2 ... u4
- -Iluf @ .... @ (ut w(-1) @ @ 1
mmxx(2//o 2,2 2) ||:112 ... llu 11 |
For all E [d] and E [T..
[1[S(u) @ .... 8 ut @ ... @ uf-1)113 - ||/| c .o...8.. ..... 8....u/f1l u l
S mmax(2 2a,//// 1 || ... 1/
For all [d] and [t].
ut ut
S
U @ 2
8.... 80...00 @uf
+ S(1) 8 ... 2 n 8 ... 2 n
|uf w/
up ut=1
8 ... 69 ui
+ r
30 ... 60 uf-1
uf=1ll2
up
ux
S maxx(2/o ,, 221/a
+
11
| 112
11 ... -11u
|u
u/ 1
where tensor Frobenius norm ||>||| = Il ||u//l2 and u/ is the closest point to w in (T....
For the desired accuracy >> in the final guarantee ② in what follows correspondingly define sequence of distortion levels En c, 2
= 24/"e for L x [ogz(nd) levels and let L max(0, |a loollog2222/ [1 such that for L, Et < therefore max(e1, <?) = ej. Additionally, define x # 8 69 u being the finest level of approximation. Give e, n, d, will pick L = C (1dlg)(nd) for a constant C' and work under the assumption that L I L in the proofs presented Section B the case when ī. > T. allows us to draw the same conclusion and is deferred Here the constant C is independent from all problem parameters.
to Appendix D
Definition 3 takes center stage in the following lemma. The trade-off of Tjt, e and pt specified in the proof of Lemma 4 below ensures that there's 's no occurrence of / in the final stated m. The {ei) } plays the role of multi-level approximation close in spirit to what the 7-functional attempts to capture. The super-exponential factor of dd also made an appearance in earlier work on embedding of finite set using Tensor-SRHT
Lemma 4 (Multi-resolution embedding property of row-wise tensored sketches). With m
O(C (d' + (1+ )/"))²)),, Tensor-SRHT defined in Definition [ satisfies Definition 3 for a = 2/d. The same property also holds for Tensor Subgaussian defined in Definition for m O ( 2d (1+ (1+n)d)/e? and a = 2/d.
4.3 Embedding of general sets with row-wise tensored sketches
Now we embark on our journey for the proof of our main result on row-wise Kronecker-structuree sketches where Definition S and Lemma f will reveal their power.
Theorem 2 (Gordon-type Inequality for Rensor-SRHT and Tensor Sunsor-Subgaussinn) Tensor-SRHi
with m " (EEn (2) satisfies uniform concentration Q The same guarantee
carries over to Sunsor-Subgaussicn with O 2 Vizi 22)

---

This recovers the result of [1]] for d = (ignoring poly-logs). In light of the tail bound Theorem 2.1 in [. it is also natural that the 12/d functional shows up.
Remark. This concentration result can also be easily converted to be on |||x||2 1 - 1 using basic
inequality min{la² 11, la2 11} I la 1 min[la² 1/, V - 1 for 2 0. For
short proof, see Appendix
is worth noting that the above argument will generalize to other structured random ensembles, e.g., partial circulant matrix with random signs. To put things in context, we compare this bound with what we got from Lemma Using Lemma
S
72/a (T*) S (1 K log2(b/a) b/a lo))(a)) 72 (2(T"))
which means substituting into Theorem
2 assuming for the sake of argument all the T are the same, focusing on the dependence and 12. this approach gives
0(12 ma (T))(
()) ((blog((a)) -7(("))((3)
(5)
if ignoring poly-logs. In contrast to Lemma 2 where we used single-scale discretization m / O -2 n 14a r()) ), Sudakov informs us
/blog(a) sup cvblog(a/c) x 72(T)) S vn. <E(0,1]
Therefore in the case of low complexity set (12(T) < vn), the multi-resolution approach pays off.
5 Recursive Kronecker Embedding
The row-wise-tensored mapping from the previous section, despite its simplicity, gives exponential dependency the degree d (and necessarily so, preview for Section F), suggesting it is ideal for embedding low-degree tensor. In this section, we analyze the "sketch and reduce" approach proposed by (2) which composes degree-2 sketches from the previous section in the following way: we define the operation S acting on rank-1 1 e.g., degree-3 tensor as
(6) The distinctive feature of the design that each layer, the Kronecker-structured sketch S only acts on degree-2, reduced-diimensional tensor something it excels at. is an easy exercise that the matrix S E mm"x"" when acting on rank-1 degree-d tensor, can be deemed S = Q" for
8 2) == S* S 8²)).
Q = 1 and Q* S (Q* @ I,) E gmxxa= R41 for k = d, ......... ...
where each S* p for E [d 1] and Std e Rmxn
5.1
Building blocks for multi-resolution covering
The analysis follows the same template once we know how the JL moment property is preserved under matrix direct sum and multiplication, which was investigated in previous work. We have the following discrete JL property for the embedding matrix S introduced above.
Lemma (Finite Set Embedding Property). The recursive embedding (6) satisfies S2 - 1/
max(e, e?) for all unit-norm, rank-1 I tensors I belonging finite set of cardinality p with probability at least 1 - for any 0 with O ( (log" (p) + +1² V n)). Moreover, such operation be conducted in time O(d(n log + m)) when each St is constructed from an degree-2 Tensor-SRHT sketch.
The ensuing lemma makes it clear that we should be grateful for the result stated above.
Lemma 6 (Multi-resolution embedding property of Recursive Tensor-SRHT), With m Od - + //e)) Recursive Tensor-SRHT satisfies the (e. n,, Multii- Embedding Property in Definition 3 with = L.
7

---

5.2 Embedding of general set using recursive sketch
We will employ a slightly different decomposition of the chain for this construction and dedicate the section to prove the following theorem. At a high level, the observation is that the sketch, albeit taking complicated hierarchical form, happens to be linear when acting on rank-1 tensor. Therefore the strategy is to have all the terms in the chain we need to control in the rank-1 form that only involves difference in one factor, after which the multi-resolution embedding property can be repeatedly instantiated as before.
Theorem (Gordon-type Inequality for Recursive Kronecker Embedding). The Recursive Tensor- SRHT with m = O(de 2 "iin (1 (dl + (1+ + r))²)) satisfies |||x|| - 1 S max(e, e²) for all - u² @ ... & ud E T x ................................ T with probability least - exp( (1)(-)))2 ()) for d 2 2.
enlightening to compare with the previous embedding bound, assuming again the covering number admits N(T sB²) I (9) for all i [d]. With +
we have
m(T) S C₁ / log N(T .B)) ds S SCCSCA S, blogía/s) C1 blog(a)
which means using Theorem that Od (a)/e)) for the desired embedding guarantee. This is favorable as the dependence on d has been reduced from exponential to polynomial. For example we can see that when each 7" consists of set of points the unit sphere, b = o(1) and
p we get log" (p)/e² opposed to log" (p)/e2 from the previous section ( when focusing on the scaling with p.
Applications
In this section, we give applications of our result in two settings, deploying one type of random embedding for each, where we see how these bounds can take advantage of the underlying low complexity structure to move away from the (potentially much larger) ambient dimension. We note that these applications crucially exploit the fact that the object in R= being acted upon has Kronecker structure - this departs from e.g., oblivious subspace embedding (OSE) result from I where the column span of any nd x p matrix preserved.
6.1 Signal Recovery
Inspired by compressed sensing, suppose we are given independent random (linear) I-subgaussian measurements on Kronecker-structured rank-1 signal of type
y4 (S,, x) = II (vf u²), i [m]] j=1
for r = u² ... u
2...Quu
ET c 1 and would like to know when does performing
Σ fx') subject to S(z @ ....@ ....0 x = fz())) < R2 [d (x) fe ES
min
(8)
uniquely reconstruct æ, where fy above is convex and R, := (w²) encodes the prior knowledge we have so that {u²} is feasible. In the case when such information not available, the constraint can simply read as || ll2 S 1, for example. Notice that the decision variable lives in lower dimensional space (nd as opposed to nd if we naively vectorize the signal) and one candidate could be alternating projected gradient descent over each factor. Computation aside which algorithm to enlist for solving Sb (it involves solving a non-convex problem due to the multi-linear structure), the analysis lower bound on the sample complexity for successful recovery. The following quantities facilitate the analysis.
below gives an information-theoree
Definition 4 (Descent Cone and Restricted Singular Value). We use D(Jj, u²) ) to denote the descent cone of convex function f3 point w³ E R", that is, P(5y,w)
Ursoft E R=: fy(ui + Tl) < [z(w0)}. The correspondingly normalized descent cone is demoted as D(J,, w) = ::::=D]pp w/ - Let amin (S;C) C) be the minimum singular value of a matrix S restricted to set C, ie., m (S;C)= =
min [[Sz]], Furthermore, the descent cone of a proper convexfunction is always convex.
8

---

We take hints from 8 for the lemma below.
Lemma (Recovery Guarantee). If [|SSw/l 2 (1 (1--) [|]|||||
for for all w (u' + + +=)ns== 8.. ..... (u
(d) 1--5m-1 for which t E D(ff, ud) where e 1, the optimizer {21 returned by satisfies
@ & _ u @ ... @ u for the measurement model 7
Invoking Theorem with Tensor- Subgaussaaa, for (0, Ve W ... x W where W = (u² + Dfj ns"-!,
|||S||| 111 S min[ 11. 11 5 Se
picking m -O 72/a(M (d + (1+ (1++)))/=²) which means m (S: W x... Wd) 2 - > 0 as needed by Lemma
Using translation invarianne and subadditivity of the y-functionals, one could show that this is order-wise the same
-OC4(EE (D/a, u²)))² (d + (1++)))) if f, are convex E for details. Now thanks to the decoupling, it reduces to d descent cone vector
we refer to Appendix
Gaussian width type calculation.
Example 1. Supppose each of the d factors is k-sparse, i.e,, T = [ut E ER" I1''llo S k. ||u*1|2 = 1}, it is classical that the normalized descent cone for E norm at k-sparse vector is D(Ji, (') {s: || S 2//]sssl2: ||s||
1}. Since CBnv(kB n BT) C <VBB n B C conv(k n B for an absolute constant C. from known result one can deduce that the covering number and Gaussian width scale
w(D(Il 11, w²)) = v h log(enn/k) (D(II I11, u² )> x k llog(en/Ak))
consequently
(P |1,, (1,, S (kdlog(n/ (k/ log(kd)) klo(n//k).
This gives assuming log (ng(n/)) < (not worrying about the dd factor, assuming d is small for this application) with
O (K' + m)) the recovery is successful with probability at least 1 exp(-r)) when omitting poly-logs. It should be clarified that the minimizer of @ may not be unique (as in the case with f, = | 11 up to sign ambiguity- - which is the only possible one for rank- 1 tensor), but this sample complexity suffices for recovering any of the equivalent representations of the rank-1 signal under consideration.
In general, the work of 8 18 provide powerful recipe for bounding the Gaussian width of a descent cone based on duality and polar cones: for [j convex function, and w E IR" fixed point, g ~ In,
w w² DD w²)) s E inf -
720
which cries out for more applications for such structured tensor recovery problems.
6.2 Optimization
Consider an optimization (tensor decomposition) problem, where for given signal x = u² 121"-..8u" T1 x x 7d taking Kronecker structure, wish solve for
min ET" Vie(d]
||u .... 2 ddd=z @.... @ 22
In general, one could also consider the denoising version where there is noise in the observation x + e, but for simplicity we focus on the noiseless case below. With the hope of saving storage and speeding up, we apply sketching before solving a lower m-dimensional problem:
min s ET" WEld
||S(u' .... 8 wd)
S(z @ @
=g(=, g(='.....,""
(10)
Let S be the recursive sketch from Section 5 and denote the optimizer of 10 (zt) Is not hard to see that since ( 2d)) I g(u), .... u O, must have S( 8-. .0.)))...))) 225) S(u² (..-es----- -uu)) which means that S restricted to set T x ... x d must have the smallest singular value bounded away from for us to uniquely identify the rank-1 factors. Note again this doesn't resolve the inherent ambiguity between the factors such as sign flips but the resulting sample complexity is sufficient to recover any such signal consistent with the measurement (i.e., the returned rank-1 solution obeys ② & ztd ut @ ..... ud hence in space it is unique). We give an example in Section

---

7 Experiments
In this section, numerically investigate (1) embedding dimension scaling with d for the two types of random embeddings in Section Hand (2) signal recovery from random Gaussian measurements as elaborated in Section 6.1 where the signal is rank-1 belonging to product of cones. This is in some sense a generalization of the non-convex Wirtinger flow formulation for the phase retrieval problem 77. where both the random measurement and the signal are non-symmetric, in addition to the availability of potential prior knowledge on the factors.
For the first experiment, we let 10, d = 5 and pick each factor {u² to be 20% sparse. The figure below reports the average distortion of the embedding |||SI||| - 1| over 25 runs for both the row-wise tensored and recursive sketch with Gaussian random factors. Variance of the distortion across the trials is also shown as we vary m = 0.8 x n x d for a E {1...., .5}. For the second experiment, perform projected gradient descent the following objective:
min
3/4
(w), 20)
(11)
SR SRR
2m
i=1
We use the spectral factorization of 1 m Ei (u) u yo ....8 (2 u )0 = m E. yo 8...8... 0..00...01
as initialization, as in expectation this is the signal = w² @ ... @ ud since we assumed vi are independent across the j's. We use the tucker-als function from the Matlab Tensor Toolbox for computing the best (1, 1, 1) tensor approximation. after which gradient update is made on each factor followed by & projection. We set each factor {u²} to be 20% sparse and let d = 3. n 10, m = x 0.8 X n x de for a E {I.... ,3} and record the successful recovery out of 25 trials. Stepsize is picked be 0.1 and success is defined [(2). 2d) S 0.1 after 500 gradient steps.
0A
6.00
68-
dicottonn 25
0:1
011
6.8
1.5
3.5
1.2
1.4
1.5
1.8
23
3.2
95
2.
samole
Anomzero degree
cample complestty taphat
"degne/
Figure 1: Left: Embedding scaling with degree. Right: Tensor recovery from Gaussian measurement.
8 Discussion
In this paper, we generalized Gordon's inequality to two families of tensor-structured random embeddings, which admit efficient implementation when acting on rank-1 Kronecker-structuue signals. As future work, deem rigorously establishing a lower bound the embedding dimension for general sets both an interesting and challenging direction to pursue. On the other hand, tools developed here should be helpful for analyzing performance of the gradient-based -aaed recovery algorithms that we numerically tested in Section ?
A Acknowledgments and Disclosure of Funding
Our sincere appreciation goes to Rachel Ward for several discussions related to the topic. This work was performed UT Austin supported under NSF IFML 2019844 and NSF 1934932.
http://www..cenoottolloo.ogg
10

---

References
[1] Thomas Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kemels. In Proceedings of the Fourteenth Annual MCMM Symposium on Discrete Algorithms, pages 141-160. SIAM, 2020.
[2] Thomas D Ahle and Jakob BT Knudsen. Almost optimal tensor sketch. arXiv preprint arXiv:1909.01821, 2019.
[3] Stefan Bamberger, Felix Krahmer, and Rachel Ward. Johnson-Lindenan Embeddings with Kronecker Structure. arXiv preprint arXiv:2106. 10t.::2906.1349,, 2021.
[4] Stefan Bamberger, Felix Krahmer, and Rachel Ward. The -ainontWrright Inequality for Random Tensors. arXiv preprint vrXiv:2106. 13345, 2021.
[5] Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson. Toward a unified theory of sparse dimen- sionality reduction in Euclidean space. Geometric and Functional Analysis, 2504):1009-1088, 2015.
[6] Jian-Feng Cai and Weiyu Xu. Guarantees of total variation minimization for signal recovery. Information and Inference: A Journal of the IMA, 4(4):328-353, 2015.
[7] Emmanuel J Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 61 61(4):1985-200) 2015.
[8] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805-
849, 2012.
[9] Sjoerd Dirksen. Tail bounds via generic chaining. Electronic Journal of Probability, 20:1-29, 2015.
[10] Sjoerd Dirksen. Dimensionality reduction with subgaussian matrices: a unified theory. Founda- tions of Computational Mathematics, 1665::136 2016.
[11] Mathieu Even and Laurent Massoulie, Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 1 134 of Proceedings of Machine Learning Research, pages 1847-1886. PMLR, 15-19 Aug 2021.
[12] Yehoram Gordon. On Milman's 's inequality and random subspaces which escape through mesh R.. In Geometric aspects of functional analysis, pages 84-106. Springer, 1988.
[13] Rafat Latala. Estimates of moments and tails of Gaussian chaoses. The Annals of Probability, 34(6):2315-22 23311, 2006.
[14] Shahar Mendelson. Upper bounds on product and multiplier empirical processes. Stochastic Processes and their Applications, (26(12):3552-366 2016.
[15] Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi. Isometric sketching of any set via the restricted isometry property. Information and Inference: A Journal of the IMA, 7(4):707-726 2018.
[16] Michel Talagrand. Upper and lower bounds for stochastic processes: modern methods and classical problems, volume 60. Springer Science & Business Media, 2014.
[17) Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized Linear Regression: Precise Analysis of the Estimation Error. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1683-1709, Paris, France, 03-06 Jul 2015. PMLR.
[18] Joel Tropp. Convex recovery structured signal from independent random linear measure- ments. In Sampling Theory, Renaissance, pages 67-101. Springer, 2015.
11

---

[19] Aad W Van Der Vaart and Jon Wellnr. Weak convergence and empirical processes: with applications statisties. Springer Science Business Media, 1996.
[20] Ramon van Handel. Chaining, interpolation and convexity II: The contraction principle. The Annals of Probubility, 4663):1764-1805, 2018.
[21] Roman Vershynin. Concentration inequalities for random tensors. Bernoulli, 26(4):3139-316) 2020.
[22] Vincent Q Vu and Jing Lei. Squared-norm empirical process in Banach space. arXiv preprint arXiv:1312.1005, 2013.
[23] Nikita Zhivotovskiy. Dimension-free bounds for sums independent matrices and simple tensors via the variational principle. arXiv preprint 0rXiv:2108.08198 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL?[N/A)
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "zHdZWwGamFr", "reviewer": "Reviewer_616B", "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. \nThe 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.\nThe 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. \nThe paper provides two applications / examples of Signal Recovery and Optimization problems that highlight the power of their results. ", "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. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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). \nThe 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. \nThe 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. \n\nWeaknesses: I am not able to flag any technical weaknesses in the paper. \nThe 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WVk1GfCvcJB", "reviewer": "Reviewer_vzAY", "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. ", "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.\n[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.\n\n2. 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.\n\n2. 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.\n\n3. The experimental evaluation of the proposed methods is limited.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n1. 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). \n2. The paper is well organized and written clearly.\n3. The potential applications are interesting, for example, the compressive sensing of tensor structured signal and tensor decomposition problems.\n\n*Weaknesses*\n1. 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.\n\n[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.\n\n2. 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.\n\n3. The experimental evaluation of the proposed methods is limited.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D6ZanT0kUEV", "reviewer": "Reviewer_Udiw", "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.", "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.\n\n2. 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", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nOverall, the paper is well-written and easy to read. The results are interesting and novel, which would certainly contribute to the field.\n\nWeakness:\n1. 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.\n2. 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.\n3. 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept