Source-linked AI summary
Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
M. A. Iwen, D. Needell, E. Rebrova, A. Zare
TL;DR
Large-scale dimension reduction needs to preserve geometry while accommodating structured data and avoiding the storage burden of massive JL maps. The paper develops modewise JL embeddings and proves results for structured tensor subspaces as well as arbitrary low-dimensional subspaces. It reports embeddings that require fewer random bits than standard methods, with applications including compressed least squares.
Problem
Dimension reduction for large tensors is challenging because their structure is complex, while existing methods often use matricization or vectorization.
Source: §1 · p. 1, §3 · p. 10Method
The paper constructs JL embeddings by applying random maps modewise to tensors, then vectorizing and applying a second JL map where needed.
Source: §1.2 · p. 3Results
The proposed embeddings require fewer random bits than standard methods for rank-one-basis tensor subspaces and arbitrary low-dimensional subspaces.
Source: §6 · p. 28Takeaways & Limitations
The results support compressed least-squares applications, including fitting low-rank CP decompositions.
Source: §1.2.1 · p. 3, §6 · p. 28The rank-one-basis result requires a coherence assumption and has worse ε dependence than the comparison result in.
Source: §1.2.1 · p. 5
Abstract
from arXiv · showhide
In this paper new general modewise Johnson-Lindenstrauss (JL) subspace embeddings are proposed that are both considerably faster to generate and easier to store than traditional JL embeddings when working with extremely large vectors and/or tensors. Corresponding embedding results are then proven for two different types of low-dimensional (tensor) subspaces. The first of these new subspace embedding results produces improved space complexity bounds for embeddings of rank-$r$ tensors whose CP decompositions are contained in the span of a fixed (but unknown) set of $r$ rank-one basis tensors. In the traditional vector setting this first result yields new and very general near-optimal oblivious subspace embedding constructions that require fewer random bits to generate than standard JL embeddings when embedding subspaces of $\mathbb{C}^N$ spanned by basis vectors with special Kronecker structure. The second result proven herein provides new fast JL embeddings of arbitrary $r$-dimensional subspaces $\mathcal{S} \subset \mathbb{C}^N$ which also require fewer random bits (and so are easier to store - i.e., require less space) than standard fast JL embedding methods in order to achieve small $\epsilon$-distortions. These new oblivious subspace embedding results work by $(i)$ effectively folding any given vector in $\mathcal{S}$ into a (not necessarily low-rank) tensor, and then $(ii)$ embedding the resulting tensor into $\mathbb{C}^m$ for $m \leq C r \log^c(N) / \epsilon^2$. Applications related to compression and fast compressed least squares solution methods are also considered, including those used for fitting low-rank CP decompositions, and the proposed JL embedding results are shown to work well numerically in both settings.
1. Motivation and Applications
The paper addresses geometry-preserving dimension reduction for large structured data, focusing on tensors whose low-dimensional structure can be difficult to capture with existing projection methods. It proposes modewise embeddings that reduce storage demands and establishes results for rank-one-basis tensor subspaces and arbitrary low-dimensional subspaces.
1. Motivation and Applications
- Low-dimensional structure makes it possible to project large sparse vectors and low-rank matrices into much smaller spaces for inference or reconstruction.The paper frames these embeddings as useful for geometry-preserving dimension reduction in large-scale applications.Source: §1 · p. 1
1.1. Tensor dimension reduction.
- Existing tensor reduction guarantees often rely on matricization or vectorization, while some methods cover only order-2 tensors or special polynomial-kernel cases.The paper seeks guarantees for projections acting directly on tensors and retaining tensor-valued representations, avoiding potentially unaffordable unfoldings and large maps.Source: §1.1 · p. 2
1.2. Our contributions.
- The proposed two-stage operator applies JL maps modewise, vectorizes the compressed tensor, and applies a second JL map; its smaller factors can be easier to store than one massive map.The approach is aimed especially at large tensor dimensions.Source: §1.2 · pp. 2–3
1.2.1. General Oblivious Subspace Embedding Results for Low-Rank Tensor Subspaces Satisfying an Incoherence Condition.
- For rank-one-basis tensor subspaces satisfying a coherence condition, the first result permits independently chosen nearly optimal JL families and supports compressed least-squares applications.Compared with, it reduces the effective intermediate-dimension dependence on r from rd^(d+1) to r^2, at the cost of worse ε dependence and a coherence assumption.Source: §1.2.1 · pp. 3, 5
1.2.2. Fast Oblivious Subspace Embedding Results for Arbitrary Tensor Subspaces.
- The second result gives fast modewise embeddings for arbitrary tensor subspaces, with neither r nor ε raised to a power of the tensor order d.The paper also derives embeddings for arbitrary vector subspaces by effectively reshaping vectors into tensors.Source: §1.2.2 · pp. 5–6
1.3. Organization.
- The paper develops tensor and JL background, proves embedding results and least-squares applications, reports experiments, and concludes with a summary of contributions.Its organization assigns these topics to Sections 2–6.Source: §1.3 · p. 6
2. Notation, Tensor Basics, & Linear Johnson-Lindenstrauss Embeddings
This section establishes tensor notation and operations, then introduces norm-preserving Johnson–Lindenstrauss embeddings and subspace arguments. It relates modewise tensor operations to matrix operations and outlines tradeoffs in proving subspace guarantees.
2. Notation, Tensor Basics, & Linear Johnson-Lindenstrauss Embeddings
- The paper uses b for the Kronecker product, ⃝ for the tensor outer product, and ˝ for function composition.Numbers in tensor subscripts can denote unfoldings, while superscripts can denote sequence elements.Source: §2 · p. 7
2.1. Tensor Basics.
- A j-mode product with a matrix changes the size of mode j, and its mode-j unfolding is the corresponding matrix product.The paper also defines fibers and matricization, which arranges mode-j fibers as columns.Source: §2.1 · pp. 7–8
2.2. Linear Johnson-Lindenstrauss Embeddings.
- Johnson–Lindenstrauss embeddings approximately preserve norms; subspace guarantees can use a covering argument or preserve basis-vector angles, with a tradeoff in accuracy.The covering approach can require a set exponential in subspace dimension, while the basis approach requires accurate angle preservation.Source: §2.1 · p. 9, §2.2 · p. 9
3. Modewise Linear Johnson-Lindenstrauss Embeddings of Low-Rank Tensors
This section develops oblivious modewise JL embeddings for low-rank tensor subspaces spanned by rank-one tensors under a modewise incoherence condition, with norm- and inner-product-preservation results and corollaries for subgaussian tensors. It also notes that the norm anti-concentration argument may not yield useful bounds for large-rank tensors.
3. Modewise Linear Johnson-Lindenstrauss Embeddings of Low-Rank Tensors
- With probability at least 1 − η, modewise JL maps preserve squared norms within relative error ε for every tensor in the rank-r subspace, given a rank-one basis satisfying the theorem’s modewise incoherence condition.The theorem draws each mode’s map from an (η/d)-optimal JL family; its stated condition requires modewise coherence below 1/(2r).Source: §3 · p. 11
3.1. Proof of the Oblivious Tensor Subspace Embedding Theorem 3.
- For rank-r Y, if each Aj is an (ε/(4d))-JL embedding of S1_j, squared-norm error is at most ε; Propositions 2 and 3 approximately preserve norms and inner products between all tensors in the set’s span.Source: §3.1 · pp. 13–14
3.2. Naturally incoherent tensor bases.
- For Tucker subspaces with sparse cores and orthogonal factor matrices, the basis coherence is zero, yielding a special-case modewise norm-preservation bound.The corollary applies the norm bound in this zero-basis-coherence setting.Source: §3.2 · pp. 14–15
- Independent mean-zero normalized K-subgaussian basis components yield maximum modewise coherence at most μ with high probability.The stated probability bound depends on tensor dimensions, rank, and a constant depending only on K.Source: §3.2 · p. 15
- Corollary 2 shows that Proposition 2 has better dependence on ε for low-rank subgaussian tensors in high-dimensional spaces.The supplied passages do not preserve the exact bound or its full conditions.Source: §3.2 · p. 16
- Corollary 3 uses Lemma 7 to give a nontrivial lower bound on the norm of a subgaussian tensor, including when r ≤ C d and n ≥ C² max{r,d}.The stated lower bound is ||Y|| ≥ 0.99α.Source: §3.2 · p. 16
- For general independent subgaussian tensors at ranks up to O(n^d), the Lemma 8 coherence estimate is too weak for Lemma 7; whether such tensor systems generally satisfy norm anti-concentration remains open.An alternative result in [61] gives a lower bound for r ≤ 0.99n^d under mild conditions, but with additional unfavorable dependence on n.Source: §3.2 · p. 16
4. Applications to Least Squares Problems and fitting CP models
This section applies modewise dimension reduction to fitting low-rank CP models and compressed least-squares problems, presenting general embedding results and a special case with improved dependence on rank and distortion. It also gives a fast, memory-efficient two-stage modewise JL embedding for tensor subspaces that preserves distances from arbitrary tensors to affine shifts, without requiring rank-one basis tensors.
4. Applications to Least Squares Problems and fitting CP models
- For CP fitting, alternating least squares updates a changing low-dimensional subspace, and modewise dimension reduction can replace each update’s solve with smaller slice-wise least-squares problems.The update decouples into n_j problems, one per mode-j slice, which can be solved in parallel; the section proposes using modewise JL embeddings for these smaller solves.Source: §4 · pp. 16–18
4.1. General Modewise JL embeddings for Tensors with Low Modewise Coherence
- Under the theorem’s assumptions, modewise compression followed by vectorization and a JL map preserves distances from X to every tensor in the target subspace with probability at least 1 - η.The theorem concerns subspaces with low modewise coherence; the paper notes that the intermediate embedding dimension affects storage and that the final JL map reduces the dimension to near-optimal order.Source: §4.1 · p. 18
- The compressed least-squares result guarantees comparable solution quality when the modewise map preserves the subspace and specified residual-related tensors, followed by a JL embedding.The conditions require the modewise map to embed all tensors in the subspace and the orthogonal residual, plus an additional set of 4r tensors.Source: §4.1 · pp. 19–20
4.2. Fast and Memory Efficient Modewise JL Embeddings for Tensors
- A special case of modewise JL embeddings is introduced as improving dependence on both distortion ε and rank r over the general construction in Theorem 4.The following subsection considers a fast tensor JL transform formed by applying fast JL transforms modewise.Source: §4.1 · p. 21
- Theorem 7’s transform pair preserves distances from any tensor X to every Y in an r-dimensional subspace L, with probability at least 1 − η.The result uses a modewise FJL transform followed by a one-dimensional FJL transform; the basis tensors of L need not be low-rank.Source: §4.2 · p. 22
- O(m1 log N + sumℓ nℓ) random bits and storage suffice, and the transform pair applies to any tensor in O(N log N) time.The bounds assume m2 ≤ m1.Source: §4.2 · p. 22
- Theorems 4 and 7 support tensor low-rank fitting because they allow an affine shift of a low-rank tensor subspace by an arbitrary fixed tensor X.Theorem 4 is more general for low-modewise-coherence subspaces with rank-one bases, supporting modewise products by a broad class of nearly optimal JL matrices; Theorem 7 uses a particular DFT-based operation.Source: §4.2 · p. 23
- For large d, Theorem 7 has a significantly better intermediate embedding dimension than Theorem 4 and yields more compactly storable multistage embeddings.Both theorems ultimately achieve a near-optimal final embedding dimension; unlike Theorem 4, Theorem 7 does not require rank-one basis tensors.Source: §4.2 · p. 23
5. Experiments
The experiments test modewise JL embeddings on randomly generated tensors and MRI data, then examine CPD reconstruction and compressed least-squares estimation of CPD coefficients.
5.1. Effect of JL Embeddings on Norm.
- Higher compression improves norm and distance preservation, while modewise methods retain norms on relatively coherent data.The experiments average over 1000 trials; the MRI results also compare runtime and norm preservation across embedding approaches.Source: §5.1 · p. 25, Figure 2 · p. 26, Figure 3 · p. 26
5.2.1. CPD Reconstruction.
- The experiments use the first of three MRI samples to study CPD reconstruction and compressed least-squares estimation of its coefficients.The sample is described as having a relatively low-rank CP representation; the study compares 1-stage and 2-stage JL with uncompressed least squares.Source: §5.1 · p. 25
- MRI relative CPD reconstruction error decreases as rank r increases.Figure 4 reports reconstruction error for different ranks.Source: Figure 4 · p. 27, §5.2.1 · p. 27
- CPD-ALS iteratively updates factor matrices until fit improvement stops or the iteration limit is reached; CORCONDIA can help choose rank and factor estimates.After solving for the factor columns, the procedure can normalize them and absorb their norms into the coefficients.Source: §5.2.1 · p. 27
5.2.2. Compressed Least Squares Performance.
- Compressed least squares estimates CPD coefficients from projected data, and its error measure compares true reconstruction error with error from the estimated coefficients.The projected problem is described as yielding an approximate solution to the uncompressed coefficient problem.Source: §5.2.2 · p. 28
6. Conclusion
The paper concludes that its modewise JL subspace embeddings are faster to generate and smaller to store than traditional JL embeddings, especially for very large tensors. It also identifies applications and directions for further work.
6. Conclusion
- The proposed modewise JL subspace embeddings are faster to generate and significantly smaller to store than traditional JL embeddings, especially for very large tensors.The conclusion also reports improved space-complexity bounds for rank-r tensors with unknown basis tensors and fewer random bits for certain vector subspaces.Source: §6 · p. 28
- The results include fast JL embeddings for arbitrary r-dimensional subspaces using fewer random bits than standard methods, alongside applications to compressed least squares and low-rank CP fitting.The paper reports experimental confirmation of these results.Source: §6 · p. 28
- Future directions include other random embeddings, embeddings that preserve additional structure such as core-tensor properties, and reconstruction and inference tasks.Source: §6 · p. 28
Appendix A. Proofs of the Tensor properties and JL Results from Section 2
Appendix A supplies proofs for tensor properties and JL results used earlier in the paper. It also establishes inner-product preservation and a covering-based argument for controlling embedding distortion.
Appendix A. Proofs of the Tensor properties and JL Results from Section 2
- The appendix proves tensor properties used throughout the paper, including identities established through mode unfoldings and reshaping.Several tensor identities are verified by translating the expressions to unfoldings and then restoring tensor form.Source: Appendix A · p. 32
- A JL embedding that preserves norms also preserves inner products among elements of a finite set, using polarization for vectors and its tensor counterpart.Source: Appendix A · p. 33
- The distortion proof extends a finite covering estimate to the whole unit sphere by bounding the operator norm and approximating each vector with a covering point.The proof treats upper and lower norm bounds separately.Source: Appendix A · pp. 33–34
Appendix B. Proofs of the Intermediate Results from Sections 3.1 and 4.1
Appendix B proves auxiliary results used in Sections 3.1 and 4.1. Its arguments use mode unfoldings, inner-product bounds, and induction across successive modewise embeddings.
Appendix B. Proofs of the Intermediate Results from Sections 3.1 and 4.1
- The appendix derives auxiliary proposition and lemma results using mode unfoldings, linearity of matricization, and tensor properties.The appendix states that these proofs establish results listed in Section 3.1.Source: Appendix B · p. 34
- The proof tracks coefficient changes and modewise coherence through successive embeddings, then uses induction to bound their cumulative behavior.The stated induction controls coefficient growth and updated coherence across modes.Source: Appendix B · p. 36
- For ε ≤ 3/4, the stated bound controls squared-norm distortion after applying the modewise embeddings.The proof obtains the bound by considering separate cases for the coherence parameter.Source: Appendix B · p. 37