Skip to content
nonconvexcard

The operator norm on a net

ProofIntermediate⏱ 30 minHigh-Dim Probabilitynetoperator normapproximation

Problem

Let N\Ncal be an ε\eps-net of Sd−1S^{d-1} with ε<1\eps<1. Prove that for any A∈Rm×dA\in\R^{m\times d},

sup⁡x∈N∥Ax∥2≤∥A∥≤11−εsup⁡x∈N∥Ax∥2.\sup_{x\in\Ncal}\|Ax\|_2 \le \|A\| \le \frac{1}{1-\eps}\sup_{x\in\Ncal}\|Ax\|_2 .

For a symmetric AA, prove the analogous statement for the quadratic form with ∥A∥≤(1−2ε)−1sup⁡x∈N∣x⊤Ax∣\|A\| \le (1-2\eps)^{-1}\sup_{x\in\Ncal}|x^\top Ax| when ε<1/2\eps<1/2.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Bounding the spectral norm by row and column sumsFoundationsProofIntermediate30 min
Frobenius versus operator norm for random matricesRandom MatricesNumericalIntermediate30 min
Measure the covariance estimation rate runHigh-Dim StatisticsCodingIntermediate1 hour
Sample complexity of covariance estimationHigh-Dim StatisticsNumericalIntermediate30 min
The volumetric lower bound on covering numbersHigh-Dim ProbabilityProofIntermediate30 min