Speaker: Mary Wooters, Stanford UniversityTitle: Sparse Recovery for Orthogonal Polynomial Transforms; zoom link @ https://sites.google.com/view/minds-seminar/homeDate: 07/30/2020Time: 2:30 PM - 3:30 PMPlace:

(Part of One World MINDS seminar: https://sites.google.com/view/minds-seminar/home) \[ \] Consider the following sparse recovery problem. We have query access to a vector x in R^N such that \hat{x} = Fx is k-sparse (or nearly k-sparse) for some orthogonal transform F. The goal is to output an approximation to \hat{x} in sublinear time. This problem has been well-studied in the special case that F is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k polylog(N)). However, for transforms F other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this talk I'll describe sublinear-time algorithms---running in time poly(k log N)---for solving the sparse recovery problem for orthogonal transforms F that arise from orthogonal polynomials. More precisely, our algorithm works for any F that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem, which works for any "flat" orthogonal polynomial transform. This is joint work with Anna Gilbert, Albert Gu, Chris Re, and Atri Rudra.

Department of Mathematics

Michigan State University

619 Red Cedar Road

C212 Wells Hall

East Lansing, MI 48824

Phone: (517) 353-0844

Fax: (517) 432-1562

- People
- All
- Regular Faculty
- Postdocs
- Fixed Term/Visiting Faculty
- Specialists and Instructors
- Adjunct Faculty
- Emeriti
- Graduate Students
- Teaching Assistants
- Staff
- Administration
- Diversity, Equity, Inclusiveness
- Faculty Honors

- Research
- Faculty Research Interests
- Seminars
- Seminars by Week
- Geometry & Topology
- MCIAM
- MathSciNet
- Institute of Mathematical Physics
- Math Library
- Phillips Lecture

- Undergraduate
- Undergraduate Program
- Class Pages
- Student Portal
- Webwork
- Math Learning Center
- Actuarial Science
- Advising Information
- Override Request
- Math Placement Service
- Herzog Competition
- Scholarships
- Exchange Program
- Sample Finals
- Multicultural Center Feasibility