Learning Trigonometric Polynomials from Random Samples and Exponential Inequalities for Eigenvalues of Random Matrices

2007/01/26 by Groechenig, Karlheinz, Poetscher, Benedikt M., Rauhut, Holger
#15A52 #42A05 #94A20 #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.math/0701781

Abstract

Motivated by problems arising in random sampling of trigonometric polynomials, we derive exponential inequalities for the operator norm of the difference between the sample second moment matrix n^-1U^*U and its expectation where U is a complex random n× D matrix with independent rows. These results immediately imply deviation inequalities for the largest (smallest) eigenvalues of the sample second moment matrix, which in turn lead to results on the condition number of the sample second moment matrix. We also show that trigonometric polynomials in several variables can be learned from const ⋅ D ln D random samples.

Related

• Mathematics of learning
• Harmonic mean, random polynomials and stochastic matrices
• Exponential concentration for the number of roots of random trigonometric polynomials
• Random trigonometric polynomials: universality and non-universality of the variance for the number of real roots
• Deriving Matrix Concentration Inequalities from Kernel Couplings