Detecting linear dependencies in a matrix Let $X$ be a matrix of $n$ rows (measurements) and $p$ columns (dimensions or features), and $n>p$.
Denote by $r(i)$ the $i$th row of $X$.
Assume that a subset of rows of $X$, denoted $r(i_j)$, where $j=1..d$, are linearly correlated, that is, without loss of generality,
$r(i_j)=a_j + b_j\cdot r(i_0) + W_j$, where $a_k,b_k$ are unknown scalars and $W_k$ is a Gaussian vector of size $p$ with small variance.
Assuming the locations $i_j$ are unknown, is there a way to detect the subset $r(i_j),j=1..d$? or even the amount of dependency? Since this is not a square matrix, the rank will be less than or equal to $p$, which is much smaller than $n$.
Thank you.
Edit/clarification:
This is different than finding the nullspace of a matrix. In a nullspace, each vector $v$ will satisfy $X'v=0$, so indeed the vector that has zeros for all indices not included in my subset and the correct weights in the subset indices will be in the kernel (as a nonzero vector that yields $X'v=0$), but seeking for the kernel will in general yield vectors that involve values from indices outside the subset as well.
 A: If a collection of points $(X_{i})_{i=1}^{n}$ lies on the line through a point $P$ with direction vector $v \neq 0$, then by definition there exist scalars $(t_{i})_{i=1}^{n}$ such that
$$
X_{i} = P + t_{i}v,\quad i = 1, \dots, n.
$$
Since the list can be recovered from the point $P$, the vector $v$, and the scalars $t_{i}$, the points $X_{i}$ have "redundancy".
If $v$ is a principal component axis and $P$ is taken to be the origin, the $t_{i}$ are the corresponding principal components of the $X_{i}$.
It's difficult to be more specific (or less tautological, depending on your point of view) without a precise definition of "redundancy".
A: If you're saying your $r(i_j)$ are approximately affinely dependent, rather than linearly dependent, you're going to have a hard time using linear algebra to solve your problem; you'll probably have to turn to a convex optimization sort of search problem. If the $r(i_j)$ are indeed approximately linearly dependent, then I would just choose the $d$ rows corresponding to the $d$ smallest singular values in the SVD of X as your $r(i_j)$.
It might help if you can come up with a way to measure the degree to which a set of vectors is linearly dependent. One way might be $\min_{\text{rank(A) = 1}} \|X - A\|$.
