3
$\begingroup$

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!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.