Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
DOI10.1016/j.acha.2024.101686MaRDI QIDQ6657418
[[Person:6081981|Author name not available (Why is that?)]], Lihong Zhi, Ke Ye
Publication date: 6 January 2025
Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)
convex optimizationsemidefinite programmingfast Fourier transformgraph theorychordal graphabelian groupFourier sum of squaresquasi-linear algorithmsparse Gram matrices
Finite abelian groups (20K01) Numerical methods for discrete and fast Fourier transforms (65T50) Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sums of squares on the hypercube
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Adaptive sparse polynomial chaos expansion based on least angle regression
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Sums of squares based approximation algorithms for MAX-SAT
- A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices
- Sums of Hermitian squares and the BMV conjecture
- Resolution for Max-SAT
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Exploiting sparsity in complex polynomial optimization
- The approximation of one matrix by another of lower rank.
- The multiple subset sum problem
- Graph Implementations for Nonsmooth Convex Programs
- An optimal minimum spanning tree algorithm
- Stable recovery of sparse overcomplete representations in the presence of noise
- Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Truncation Errors in Two Chebyshev Series Approximations
- Complexity of counting CSP with complex weights
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- Stable signal recovery from incomplete and inaccurate measurements
- Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
- Sum-of-squares hierarchies for binary polynomial optimization
- Lower bounds of functions on finite abelian groups
This page was built for publication: Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6657418)
