Almost-Orthogonal Bases for Inner Product Polynomials
summary
Provides an explicit almost‑orthogonal polynomial basis for orthogonally invariant functions of m Gaussian or spherical or Boolean vectors, with degree‑D basis elements Pg indexed by multigraphs and defined combinatorially as a signed sum over matching collections whose weights include N^{#cycles}. Key facts: E[Mg] equals the sum over perfect matching collections of N^{#cycles} so examples evaluate to N or N^2, Pg are orthogonal across different total degrees, and the spherical case can give negative inner products (K5 decomposition). Pg = sum over matching collections with sign and N^{cycles} E[Mg] = sum_{perfect matchings} N^{cycles}
AI-written summary · about
chapters (7)
related talks
29mApproximating Spherical Gaussian Mixtures
29mComputational Barriers to Estimation from Low-Degree Polynomials
35mLearning General Gaussian Mixtures With Efficient Score Matching
01h 30mAnalytic Methods for Supervised Learning IV
31mPlanted Geometric Matching Problems
45mOn Finding Modes of Gaussian Sum-Product Networks
49mRobust List Decoding of Spherical Gaussians
01h 03mHigh Dimensional Geometry and Concentration II