Computing linear sections of varieties: quantum entanglement, tensor
decompositions and beyond
- URL: http://arxiv.org/abs/2212.03851v3
- Date: Sun, 7 May 2023 21:11:17 GMT
- Title: Computing linear sections of varieties: quantum entanglement, tensor
decompositions and beyond
- Authors: Nathaniel Johnston, Benjamin Lovitz and Aravindan Vijayaraghavan
- Abstract summary: We study the problem of finding elements in the intersection of an arbitrary conic variety in $mathbbFn$ with a given linear subspace.
This problem captures a rich family of algorithmic problems under different choices of the variety.
We develop an algorithm that solves this problem efficiently for "typical" subspaces.
- Score: 8.604882842499212
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of finding elements in the intersection of an arbitrary
conic variety in $\mathbb{F}^n$ with a given linear subspace (where
$\mathbb{F}$ can be the real or complex field). This problem captures a rich
family of algorithmic problems under different choices of the variety. The
special case of the variety consisting of rank-1 matrices already has strong
connections to central problems in different areas like quantum information
theory and tensor decompositions. This problem is known to be NP-hard in the
worst case, even for the variety of rank-1 matrices.
Surprisingly, despite these hardness results we develop an algorithm that
solves this problem efficiently for "typical" subspaces. Here, the subspace $U
\subseteq \mathbb{F}^n$ is chosen generically of a certain dimension,
potentially with some generic elements of the variety contained in it. Our main
result is a guarantee that our algorithm recovers all the elements of $U$ that
lie in the variety, under some mild non-degeneracy assumptions on the variety.
As corollaries, we obtain the following new results:
$\bullet$ Polynomial time algorithms for several entangled subspaces problems
in quantum entanglement, including determining r-entanglement, complete
entanglement, and genuine entanglement of a subspace. While all of these
problems are NP-hard in the worst case, our algorithm solves them in polynomial
time for generic subspaces of dimension up to a constant multiple of the
maximum possible.
$\bullet$ Uniqueness results and polynomial time algorithmic guarantees for
generic instances of a broad class of low-rank decomposition problems that go
beyond tensor decompositions. Here, we recover a decomposition of the form
$\sum_{i=1}^R v_i \otimes w_i$, where the $v_i$ are elements of the variety
$X$. This implies new uniqueness results and genericity guarantees even in the
special case of tensor decompositions.
Related papers
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
We consider the spectral tail condition number, $kappa_ell$, defined as the ratio between the $ell$th largest and the smallest singular value of the matrix representing the system.
Some of the implications of our result, and of the use of $kappa_ell$, include direct improvement over a fine-grained analysis of the Conjugate method.
arXiv Detail & Related papers (2024-05-09T14:56:49Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - A Unifying Framework for Differentially Private Sums under Continual
Observation [20.432568247732206]
We study the problem of maintaining a differentially private decaying sum under continual observation.
We give a unifying framework and an efficient algorithm for this problem for emphany sufficiently smoothangular function.
arXiv Detail & Related papers (2023-07-18T05:04:11Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
"Statistical-computational gaps" occur in many statistical inference tasks.
We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest.
We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
arXiv Detail & Related papers (2022-11-10T00:40:37Z) - A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
We give a spectral algorithm for decomposing overcomplete order-4 tensors.
Our algorithm is robust to adversarial perturbations of bounded spectral norm.
Our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations.
arXiv Detail & Related papers (2022-03-05T17:25:37Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
We consider the problem of computing a sequence of rankings that maximizes consumer-side utility while minimizing producer-side individual unfairness of exposure.
We introduce a geometrical object, a polytope that we call expohedron, whose points represent all achievable exposures of items for a Position Based Model.
Our approach compares favorably to linear or quadratic programming baselines in terms of algorithmic complexity and empirical runtime.
Our solution can be expressed as a distribution over only $n$ permutations, instead of the $(n-1)2 + 1$ achieved with BvN decompositions.
arXiv Detail & Related papers (2022-02-07T14:43:35Z) - Unique sparse decomposition of low rank matrices [17.037882881652617]
We find a unique decomposition of a low rank matrixYin mathbbRrtimes n$.
We prove that up to some $Yin mathRrtimes n$ is a sparse-wise decomposition of $Xin mathbbRrtimes n$.
arXiv Detail & Related papers (2021-06-14T20:05:59Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
We provide a completely general algorithm for solving for the equivariant layers of matrix groups.
In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before.
Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
arXiv Detail & Related papers (2021-04-19T17:21:54Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting.
We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$.
Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
arXiv Detail & Related papers (2020-05-13T16:44:12Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.