What is the meaning or implications of the rank of a dataset for machine learning algorithms?

Consider a dataset with $$n$$ training examples and $$d$$ features.

Let $$D_{n \times d}$$ be the data matrix and $$r$$ be the rank of it.

In matrices, rank $$r$$ is generally useful in

1. Knowing the dimension of (optimal) vector space that can generate the rows or columns of the matrix.

2. Knowing the number of linearly independent rows or linearly independent columns in the matrix. Note that column rank and row rank are same for a matrix and is generally called as the rank of a matrix.

In fact, both 1 and 2 are same and just rephrased.

What is the meaning or implications of the rank $$r$$ of a dataset $$D_{n \times d}$$ for machine learning algorithms?

I know at least one example where the rank of the dataset (more specifically, the rank of a matrix that is computed from the design matrix, i.e. the matrix with your data, which I will describe more in detail below) can have an impact on the number of solutions that you can have or how you find those solutions. I am thinking of linear regression.

So, in linear regression, you have the model (written in matrix form)

$$\mathbf{y} = \mathbf{X} \beta + \epsilon$$

where

• $$\mathbf{y}$$ is an $$N \times 1$$ vector of dependent variables (i.e. the labels)
• $$\mathbf{X}$$ is an $$N \times K$$ matrix of indedendent variables (aka regressors or features)
• $$\beta$$ is an $$N \times 1$$ vector of parameters
• $$\epsilon$$ is the noise (i.e. you assume that there's some noise that corrupts the function that relates the features to the labels through the parameters)

It turns out that, if $$X$$ has full rank, then the so-called ordinary least squares (OLS) solution to the linear regression problem (i.e. the estimate of the parameters $$\beta$$), which can be denoted by

$$\hat{\beta} = \arg \min \| \mathbf{X} \beta - \mathbf{y} \|_{2},$$

is given by a closed-form expression

$$\hat{\beta}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}y \tag{1}\label{1}.$$

If you look at this equation, you see that we are computing the inverse of a matrix, and that matrix is $$\mathbf{X}^{T}\mathbf{X}$$. What if this matrix is not invertible? It turns out that you cannot invert a matrix if it's not full rank. It also turns out that, if $$\mathbf{X}$$ is not full rank, then $$\mathbf{X}^{T}\mathbf{X}$$ wouldn't also be (see this and this), so we couldn't use the closed-form solution \ref{1} to solve the linear regression problem, i.e. we wouldn't have anymore a convex problem (i.e. a unique solution).

So, this is the only implication of the rank of the dataset (or design matrix) has on the machine learning algorithm that I am aware of and comes to my mind right now, but it's possible that the rank can play other roles.