## UC Berkeley / Lawrence Berkeley Laboratory

#### Robust and efficient recovery of sparse spherical harmonic expansions via l1 minimization

**Rachel Ward, Courant Institute, New York University**

##### January 19th, 2011 at 4–5PM in 891 Evans Hall [Map]

Compressive sensing has triggered significant research activity in recent
years. It predicts that sparse signals can be recovered from what was
previously believed to be highly incomplete information. One of the main
results in compressed sensing can be interpreted as follows: any trigonometric
polynomial of degree *N* which is *s*-sparse, or has at most *s*
nonzero coefficients, may be efficiently recovered from
*O*(*s* log^{4}(*N*)) uniformly distributed point
samples on the domain. In this talk, we extend the scope of compressive
sensing to the recovery of
polynomials with a sparse expansion in Legendre basis. In particular, we show
that a Legendre *s*-sparse polynomial of maximal degree *N* can be
recovered from *O*(*s* log^{4}(*N*)) random samples that
are chosen independently according to the Chebyshev probability measure. As a
byproduct, we obtain condition number estimates for preconditioned random
Legendre matrices that should be of interest on their own. Finally, we discuss
generalizations of our results to the recovery of sparse spherical harmonic
expansions from randomly located samples on the sphere. Sparse spherical
harmonic expansions were recently exploited with good numerical success in the
spherical inpainting problem for the cosmic microwave background, but so far
this problem had lacked a theoretical understanding.

This is joint work with Holger Rauhut.