# Linearly independent functions evaluated at random points create full rank matrices

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

• 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. – Kostya_I Jul 20 at 20:46
• 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)$ – mohi Jul 20 at 21:05
• and what are $x_i$? – Kostya_I Jul 20 at 21:31
• $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. – mohi Jul 20 at 22:59