Skip to content
nonconvexcard

From distance preservation to inner-product preservation

ProofIntermediate⏱ 30 minHigh-Dim Probabilityjlpolarisationinner productkernels

Problem

Assume a linear map AA satisfies (1−ε)∥v∥22≤∥Av∥22≤(1+ε)∥v∥22(1-\eps)\|v\|_2^2 \le \|Av\|_2^2 \le (1+\eps)\|v\|_2^2 for all vv in the set {xi±xj}\{x_i\pm x_j\}. Prove that for all i,ji,j,

∣⟨Axi,Axj⟩−⟨xi,xj⟩∣≤ε2(∥xi∥22+∥xj∥22).\big|\langle Ax_i,Ax_j\rangle - \langle x_i,x_j\rangle\big| \le \frac\eps2\big(\|x_i\|_2^2+\|x_j\|_2^2\big).

Deduce that unit vectors have their cosine similarities preserved to additive ε\eps.

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

Hints

Hints — 0 of 3 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
Equality in Cauchy–SchwarzFoundationsProofBeginner15 min
Johnson–Lindenstrauss dimension arithmeticHigh-Dim ProbabilityNumericalBeginner15 min
Implement random projection and measure the distortion runHigh-Dim ProbabilityCodingIntermediate1 hour
The chi-squared moment generating function and its Chernoff boundHigh-Dim ProbabilityProofIntermediate30 min
Rademacher projections work tooHigh-Dim ProbabilityProofAdvanced1 hour