Minimal length in an orbit closure as a semiclassical limit

• URL: http://arxiv.org/abs/2004.14872v2
• Date: Mon, 24 Oct 2022 19:31:05 GMT
• Title: Minimal length in an orbit closure as a semiclassical limit
• Authors: Cole Franks and Michael Walter
• Abstract summary: Invariant theory states that orbit of a vector v is separated from the origin if and only if some homogeneous invariant is nonzero on v. This connection to optimization has led to efficient algorithms for many problems in invariant theory. We provide a new and independent elementary proof inspired by the Fourier-analytic proof of the local central limit theorem.
• Score: 1.6312226592634047
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider the action of a connected complex reductive group on a finite-dimensional vector space. A fundamental result in invariant theory states that the orbit closure of a vector v is separated from the origin if and only if some homogeneous invariant polynomial is nonzero on v, i.e. v is not in the null cone. Thus, efficiently finding the minimum distance between the orbit closure and the origin can lead to deterministic algorithms for null cone membership, an important polynomial identity testing problem including the non-commutative Edmonds problem. This connection to optimization has recently led to efficient algorithms for many problems in invariant theory. Here we explore a refinement of the famous duality between orbit closures and invariant polynomials, which holds that the following two quantities coincide: (1) the logarithm of the Euclidean distance between the orbit closure and the origin and (2) the rate of exponential growth of the 'invariant part' of $v^{\otimes k}$ in the semiclassical limit as k tends to infinity. This result can be deduced from work of S. Zhang (Geometric reductivity at Archimedean places, 1994), which uses sophisticated tools in arithmetic geometry. We provide a new and independent elementary proof inspired by the Fourier-analytic proof of the local central limit theorem. We generalize the result to projections onto highest weight vectors and isotypical components, and explore connections between such semiclassical limits and the asymptotic behavior of multiplicities in representation theory, large deviations theory in classical and quantum statistics, and the Jacobian conjecture as reformulated by Mathieu. Our formulas imply that they can be computed, in many cases efficiently, to arbitrary precision.

Related papers

• A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization [0.0]
  We study a connection between a Hermitian version of the SoS hierarchy, related to the quantum de Finetti theorem. We show that previously known HSoS rounding algorithms can be recast as quantizing an objective function.
  arXiv  Detail & Related papers  (2024-11-06T17:09:28Z)
• Inapproximability of Sparsest Vector in a Real Subspace [1.9943009191774073]
  We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace. We show that it is NP-Hard to approximate the sparsest vector in a subspace within any constant factor.
  arXiv  Detail & Related papers  (2024-10-03T16:22:07Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Global optimality under amenable symmetry constraints [0.5656581242851759]
  We show the interplay between convexity, the group, and the underlying vector space, which is typically infinite-dimensional. We apply this toolkit to the invariant optimality problem. It yields new results on invariant kernel mean embeddings and risk-optimal invariant couplings.
  arXiv  Detail & Related papers  (2024-02-12T12:38:20Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  We analyze inexact and versions of the CGALP algorithm developed in the authors' previous paper. This allows one to compute some gradients, terms, and/or linear minimization oracles in an inexact fashion. We show convergence of the Lagrangian to an optimum and feasibility of the affine constraint.
  arXiv  Detail & Related papers  (2020-05-11T14:52:16Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.