A variation of the well-known Johnson-Lindenstrauss transform (JLT) asserts that for $x_1,\ldots,x_m\in\mathbb{R}^n$ there exists a linear transformation $A:\mathbb{R}^n\to\mathbb{R}^k$ with $k=\mathcal{O}(\log(m)\epsilon^{-2})$ s.t.:

$$|\langle x_i,x_j\rangle-\langle Ax_i,Ax_j\rangle|\leq \epsilon \|x_i\|_2\|x_j\|_2$$ holds for all $i,j$. I was wondering if something is known about the following "Hoelder conjugate" generalization of the JLT. We are given vectors $x_1,\ldots,x_m,y_1,\ldots,y_m\in\mathbb{R}^n$ and want linear transformations $A,B:\mathbb{R}^n\to\mathbb{R}^k$ s.t.

$$|\langle y_i,x_j\rangle-\langle Ay_i,Bx_j\rangle|\leq \epsilon \|y_i\|_{p}\|x_j\|_{p'}$$, where $p'$ is the Hoelder conjugate of $p\geq1$. How big does $k$ have to be in terms of $n,m,\epsilon$? Are there probabilistic constructions for $A,B$? Thanks in advance!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.