1
$\begingroup$

Assume $f_1, f_2,...,f_n: \mathbb{R}^d\mapsto\mathbb{R}^d$ are linearly independent functions. Now let $w_1,w_2,..,w_k\in\mathbb{R}^d$ be i.i.d. Gaussian random vectors distributed as $\mathcal{N}(0,\mathbf{I}_d)$ and $v_1,\ldots,v_k\in\mathbb{R}$ are i.i.d. Radamacher random variables ($\pm 1$ with equal probability). I want to show that as long as $kd\ge n$ then with high probability the matrix

\begin{align*} \begin{bmatrix} v_1f_1(\mathbf{w}_1) & v_1f_2(\mathbf{w}_1) & \ldots & v_1f_n(\mathbf{w}_1)\\ v_2f_1(\mathbf{w}_2) & v_2f_2(\mathbf{w}_2) & \ldots & v_2f_n(\mathbf{w}_2)\\ \vdots & \vdots & \ddots & \vdots\\ v_kf_1(\mathbf{w}_k) & v_kf_2(\mathbf{w}_k) & \ldots & v_kf_n(\mathbf{w}_k) \end{bmatrix}\in\mathbb{R}^{kd\times n} \end{align*} is full rank

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "linearly independent functions"? If it's just that there's no linear combination that vanishes identically, then it can still be that $f_n$ vanishes in a ball of radius $e^n$ around the origin. Which means that with overwhelming probability your matrix will have a zero column. $\endgroup$
    – Kostya_I
    Commented Jul 20, 2019 at 20:46
  • $\begingroup$ yes no linear combination that vanishes identically. To avoid pathological cases like you state above. Let's assume f is sufficiently nice that this doesn't happen e.g. f is smooth and differentiable. Specifically I'm interested in the case where $f_i(w_j)=\phi'(w_j^Tx_i)x_i$ with $\phi(z)=\log(1+e^z)$ $\endgroup$
    – mohi
    Commented Jul 20, 2019 at 21:05
  • 1
    $\begingroup$ and what are $x_i$? $\endgroup$
    – Kostya_I
    Commented Jul 20, 2019 at 21:31
  • $\begingroup$ $x_1,...,x_n\in\mathbb{R}^d$ are n points in $\mathbb{R}^d$ none of which can be written as a positive multiple of the other (i.e. $x_i=\alpha x_j$ for some positive $\alpha$. See mathoverflow.net/questions/336543/… for a related question of mine about the independent part. $\endgroup$
    – mohi
    Commented Jul 20, 2019 at 22:59

0

Reset to default

You must log in to answer this question.