CS Paper Radar

Improving TensorSketch Using Complex Random Variables

Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

cs.DS cs.AIstat.ML ·submitted 2026-08-11 05:59 UTC · v1

Abstract

\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

Closest papers

Nearest neighbours by meaning across the whole index.

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

cs.LG cs.DS ·2026-09-16 ·Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma
similarity 0.66
Abstract

We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% ~\cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$. Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in $\mathbb{R}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in $\mathbb{R}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with $p$. In this work, we address this limitation by proposing a sketching-based estimator that requires $O\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.

0.29

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics

cs.LG cs.DSmath.PRmath.ST ·2026-10-28 ·Aniket Das, Tselil Schramm
similarity 0.60
Abstract · Companion paper to arXiv:2610.16705 (Part I). 71 pages, 1 figure

We consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in $\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. Continuing the program initiated in Part I [arXiv:2610.16705], we show that spherical Langevin dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Together with Part I, our results demonstrate that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.

0.14

A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings

cs.DS ·2026-08-28 ·Lorenzo Beretta, Cameron Musco
similarity 0.59
Abstract

We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm ε)$ error, Bujanović et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/ε^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/ε^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/ε^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.

0.38

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.58
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25

Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

cs.LG ·2026-09-28 ·Yueming Lyu
theory similarity 0.57
Abstract

Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the $n$ points serve as a design matrix $X\in\mathbb{R}^{n\times d}$ for a feature map, however, computing $Ψ(X)^\top v$ or $Ψ(X)w$ for an elementwise nonlinearity $Ψ$ costs $O(nd)$ time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator $(1,t,\dots,t^{d-1})$ uses a scalar $t$ of fixed multiplicative order $m$. Splitting $\mathbb{F}_n^\times$ into cosets of $\langle t\rangle$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $Ψ$ in $O(n\log m)$ time and $O(n)$ memory, without forming $X$. Since fixing $m$ falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial $Φ_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(α-1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(ζ_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $Θ(m-1)$. Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with $d=2048$, $n\approx4.1\times10^7$ in 2.3 ms.

0.27

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.57
Abstract

Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $δ\|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $δ$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.

0.32

SparseStack Is an Optimal Oblivious Subspace Embedding

cs.DS math.NA ·2026-09-02 ·Diar Heidary
theory similarity 0.57
Abstract · The proof was developed with AI systems

We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): $m=O((d+\log(1/δ))/\varepsilon^2)$ rows and $s=O(\log(d/δ)/\varepsilon)$ nonzero entries per column for distortion $\varepsilon$ and failure probability $δ$ on any fixed $d$-dimensional subspace, with explicit constants. The proof turns random-matrix concentration into a problem in finite-dimensional linear algebra. A coupling first reduces the moment estimates to a model with independent finite-valued entries. We represent these variables by multiplication operators, so their matrix moments become exact matrix elements of a deterministic operator on a finite tensor product. The central estimate bounds the contribution of $\ell\ge1$ occupied sites sharing the external factor $\mathbb{R}^d$ by $d+\ell-1$ rather than $d\ell$, yielding additive dependence on the dimension and the moment order. This approach controls both spectral edges without Gaussian comparison. The main theorem has been formally verified in Lean 4.

0.40

Efficient Recovery of Latent Coordinate Structure from Sparse Observations of the Hypercube

cs.DS ·2026-10-08 ·Rares-Darius Buhai, Davide Mazzali, Weronika Wrzos-Kaminska
theory similarity 0.57
Abstract

Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=2^d$ vertices, each corresponding to a distinct "feature" vector in $\{\pm 1\}^d$. Between each pair whose feature vectors are at Hamming distance one, an edge is observed independently with probability $p$. As long as the expected degree $pd$ is $\gtrsim \log d = \log \log n$, we give a polynomial-time algorithm that, given only the graph of observed edges, correctly recovers the entire feature vector of all but a vanishing fraction of vertices. This matches the information-theoretic guarantee of Kapralov, Trevisan, and Wrzos-Kaminska in polynomial rather than exponential time, resolving the algorithmic question left open by their work. Our algorithm combines a degree-$4$ sum-of-squares certificate for the structure of balanced near-minimum cuts with a rounding scheme originally developed for tensor decomposition by Ma, Shi, and Steurer (2016). The analysis relies on two novel ingredients: a sum-of-squares version of the Friedgut-Kalai-Naor theorem in Boolean Fourier analysis and a spectral concentration result for the observed subgraph of the hypercube. Finally, we provide a justification for why higher-degree sum-of-squares might be needed by showing a limitation of the basic SDP relaxation of this problem.

0.27