Do you want to publish a course? Click here

Certifying Numerical Decompositions of Compact Group Representations

389   0   0.0 ( 0 )
 Publication date 2021
and research's language is English




Ask ChatGPT about the research

We present a performant and rigorous algorithm for certifying that a matrix is close to being a projection onto an irreducible subspace of a given group representation. This addresses a problem arising when one seeks solutions to semi-definite programs (SDPs) with a group symmetry. Indeed, in this context, the dimension of the SDP can be significantly reduced if the irreducible representations of the group action are explicitly known. Rigorous numerical algorithms for decomposing a given group representation into irreps are known, but fairly expensive. To avoid this performance problem, existing software packages -- e.g. RepLAB, which motivated the present work -- use randomized heuristics. While these seem to work well in practice, the problem of to which extent the results can be trusted arises. Here, we provide rigorous guarantees applicable to finite and compact groups, as well as a software implementation that can interface with RepLAB. Under natural assumptions, a commonly used previous method due to Babai and Friedl runs in time O(n^5) for n-dimensional representations. In our approach, the complexity of running both the heuristic decomposition and the certification step is O(max{n^3 log n, D d^2 log d}), where d is the maximum dimension of an irreducible subrepresentation, and D is the time required to multiply elements of the group. A reference implementation interfacing with RepLAB is provided.



rate research

Read More

These notes are an expanded version of a talk given by the second author. Our main interest is focused on the challenging problem of computing Kronecker coefficients. We decided, at the beginning, to take a very general approach to the problem of studying multiplicity functions, and we survey the various aspects of the theory that comes into play, giving a detailed bibliography to orient the reader. Nonetheless the main general theorems involving multiplicities functions (convexity, quasi-polynomial behavior, Jeffrey-Kirwan residues) are stated without proofs. Then, we present in detail our approach to the computational problem, giving explicit formulae, and outlining an algorithm that calculate many interesting examples, some of which appear in the literature also in connection with Hilbert series.
We describe a new algorithm, the $(k,ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special inst ances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the $(k,ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.
We describe a new algorithm, the $(k,\\ell)$-pebble game with colors, and use\nit obtain a characterization of the family of $(k,\\ell)$-sparse graphs and\nalgorithmic solutions to a family of problems concerning tree decompositions of\ngraphs. Spe cial instances of sparse graphs appear in rigidity theory and have\nreceived increased attention in recent years. In particular, our colored\npebbles generalize and strengthen the previous results of Lee and Streinu and\ngive a new proof of the Tutte-Nash-Williams characterization of arboricity. We\nalso present a new decomposition that certifies sparsity based on the\n$(k,\\ell)$-pebble game with colors. Our work also exposes connections between\npebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and\nWestermann and Hendrickson.\n
The stochastic partial differential equation approach to Gaussian processes (GPs) represents Matern GP priors in terms of $n$ finite element basis functions and Gaussian coefficients with sparse precision matrix. Such representations enhance the scalability of GP regression and classification to datasets of large size $N$ by setting $napprox N$ and exploiting sparsity. In this paper we reconsider the standard choice $n approx N$ through an analysis of the estimation performance. Our theory implies that, under certain smoothness assumptions, one can reduce the computation and memory cost without hindering the estimation accuracy by setting $n ll N$ in the large $N$ asymptotics. Numerical experiments illustrate the applicability of our theory and the effect of the prior lengthscale in the pre-asymptotic regime.
Let G be a topological compact group acting on some space Y. We study a decomposition of Y-indexed stochastic processes, based on the orthogonality relations between the characters of the irreducible representations of G. In the particular case of a Gaussian process with a G-invariant law, such a decomposition gives a very general explanation of a classic identity in law - between quadratic functionals of a Brownian bridge - due to Watson (1961). Several relations with Karhunen-Lo`{e}ve expansions are discussed, and some applications and extensions are given - in particular related to Gaussian processes indexed by a torus.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا