Answers.Body: <p>I know at least one example where the rank of the dataset (more specifically, the rank of a matrix that is computed from the <a href="https://en.wikipedia.org/wiki/Design_matrix" rel="nofollow noreferrer">design matrix</a>, 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.</p>
  <p>So, in linear regression, you have the model (written in matrix form)</p>
  <p><span class="math-container">$$
  \mathbf{y} = \mathbf{X} \beta + \epsilon
  $$</span></p>
  <p>where</p>
  <ul>
  <li><span class="math-container">$\mathbf{y}$</span> is an <span class="math-container">$N \times 1$</span> vector of dependent variables (i.e. the labels)</li>
  <li><span class="math-container">$\mathbf{X}$</span> is an <span class="math-container">$N \times K$</span> matrix of indedendent variables (aka regressors or features)</li>
  <li><span class="math-container">$\beta$</span> is an <span class="math-container">$N \times 1$</span> vector of parameters</li>
  <li><span class="math-container">$\epsilon$</span> 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)</li>
  </ul>
  <p>It turns out that, if <span class="math-container">$X$</span> has full rank, then the so-called <strong>ordinary least squares (OLS)</strong> solution to the linear regression problem (i.e. the estimate of the parameters <span class="math-container">$\beta$</span>), which can be denoted by</p>
  <p><span class="math-container">$$
  \hat{\beta} = \arg \min \| \mathbf{X} \beta - \mathbf{y} \|_{2},
  $$</span></p>
  <p>is given by a <strong>closed-form</strong> expression</p>
  <p><span class="math-container">$$\hat{\beta}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}y \tag{1}\label{1}.$$</span></p>
  <p>If you look at this equation, you see that we are computing the inverse of a matrix, and that matrix is <span class="math-container">$\mathbf{X}^{T}\mathbf{X}$</span>. 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 <span class="math-container">$\mathbf{X}$</span> is not full rank, then <span class="math-container">$\mathbf{X}^{T}\mathbf{X}$</span> wouldn't also be (see <a href="https://www.statlect.com/fundamentals-of-statistics/multicollinearity" rel="nofollow noreferrer">this</a> and <a href="https://math.stackexchange.com/a/1026628/168764">this</a>), 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 <a href="https://math.stackexchange.com/a/105361/168764">unique solution</a>).</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-01T14:43:27.737Z
Answers.LastActivityDate: 2021-07-01T14:43:27.737Z
Answers.UserDisplayName: nbro
Body: <p>Consider a dataset with <span class="math-container">$n$</span> training examples and <span class="math-container">$d$</span> features.</p>
  <p>Let <span class="math-container">$D_{n \times d}$</span> be the data matrix and <span class="math-container">$r$</span> be the rank of it.</p>
  <p>In matrices, rank <span class="math-container">$r$</span> is generally useful in</p>
  <ol>
  <li><p>Knowing the dimension of (optimal) vector space that can generate the rows or columns of the matrix.</p>
  </li>
  <li><p>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.</p>
  </li>
  </ol>
  <p>In fact, both 1 and 2 are same and just rephrased.</p>
  <p>What is the meaning or implications of the rank <span class="math-container">$r$</span> of a dataset <span class="math-container">$D_{n \times d}$</span> for machine learning algorithms?</p>
  
Tags: <machine-learning><terminology><datasets><math>
Title: What is the meaning or implications of the rank of a dataset for machine learning algorithms?
UserDisplayName: hanugm
ThreadText: # What is the meaning or implications of the rank of a dataset for machine learning algorithms?
  
  (Asked by: username_0 on 2021-06-25)
  
  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?
  
  **Tags:** machine-learning, terminology, datasets, math
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-07-01. Score: 2
  
  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](https://en.wikipedia.org/wiki/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](https://www.statlect.com/fundamentals-of-statistics/multicollinearity) and [this](https://math.stackexchange.com/a/1026628/168764)), 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](https://math.stackexchange.com/a/105361/168764)).
  
  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.
  
  
  ---
  
  