Computing the standard inner product between two vectors a, b ∈ Rⁿ requires n multiplications and additions. When the dimension n is huge (say, e.g., of the order of 10¹², or larger), even computing a simple inner product can be computationally prohibitive.

Transcribed Image Text:

Let us define a random vector r ER" constructed as follows: choose uniformly at random an index i = {1,...,n}, and set r; = 1, and r;= 0 for ji. Consider the two scalar random numbers a, b that represent the "random projections" of the original vectors a, b along r: Prove that ã = r¹a = a₁, b = r¹b = b₁. nE{ab} = a¹b, that is, nāb is an unbiased estimator of the value of the inner product ab. Observe that computing não requires very little effort, since it is just equal to najb;, where i is the randomly chosen index. Notice, however, that the variance of such an estimator can be large, as it is given by ¹ [a²b² - (a + b)² k=1 var{nab}= (prove also this latter formula). Hint: let e; denote the i-th standard basis vector of R"; the random vector r has discrete probability distri- bution Prob{r = e;} = 1/n, i = 1,...,n, hence E{r} = 11. Further, observe that the products rr¡ are equal to zero for k ‡ j and that the vector r² = [...] has the same distribution as r. Generalizations of this idea to random projections onto k-dimen- sional subspaces are indeed applied for matrix-product approxima- tion, SVD factorization, and PCA on huge-scale problems. The key theoretical tool underlying these results is known as the Johnson- Lindenstrauss lemma.