Return to Question

Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that if $n$ is sufficiently larger than $d$, then $Z$ has full rank $\min(m,d)$ with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d)$.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset $\{i,j\}$ of distinct indices uniformly from ${n \choose 2}$, the collection of two-element subsets of $\{1,\ldots,2\}$
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that if $n$ is sufficiently larger than $d$, then $Z$ has full rank $\min(m,d)$ with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d)$.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Let $d$, $n$, and $m$ be large positive integers with $n$ sufficiently larger than $d$. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that $Z$ has full rank $\min(m,d)$ with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d)$.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that if $n$ is sufficiently larger than $d$, then $Z$ has full rank $\min(m,d)$ with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d)$.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Let $d$, $n$ and $m$ be large positive integers with $m$ and $n$ much larger than $d$. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Let $G := Z^\top Z$.

Question. Is true that $G$ is invertible with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d) = d$, implying that $G$ is invertible a.s.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Let $d$, $n$, and $m$ be large positive integers with $n$ sufficiently larger than $d$. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that $Z$ has full rank $\min(m,d)$ with high-probability ?

My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d)$.

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries