How does the least squares solution change if we add redundant rows?

Question

Let $\mathbf{Ax} = \mathbf{b}$ represent a set of linear equations, where, $\mathbf{A}\in\mathrm{R}^{m\times n} (m > n)$, $\mathbf{x}\in\mathrm{n\times 1}$. It is known that $\mathbf{A}$ has rank $n$. By using least squares method, one can estimate $\mathbf{x}$. Now, let us add some redundant rows to $\mathbf{A}$ so that the new rows are integer multiples of one or more of $m$ rows. Let the new matrix be called $\mathbf{A}_1$. If $\mathbf{x}_1$ is the new solution for $\mathbf{A}_1\mathbf{x}_1 = \mathbf{b}$, how does $\mathbf{x}_1$ differ from $\mathbf{x}$?

In general, what is the effect on the least squares solution if we add redundant rows to $\mathbf{A}$?

Answer 1

By doing that, you give more importance to the rows that have been copied. The solution will be closer to the subspaces corresponding to the redundant equations. The only time there won't be change is where the original solution $x$ satisfied exactly the equations that are copied.

Answer 2

Suppose we have the overdetermined linear system in $\mathrm x \in \mathbb R^n$

$$\mathrm A \mathrm x = \mathrm b$$

where $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm b \in \mathbb R^m$ are given, and $m > n$. The normal equations are

$$\mathrm A^{\top} \mathrm A \mathrm x = \mathrm A^{\top} \mathrm b$$

If $\mathrm A$ has full column rank, then $\mathrm A^{\top} \mathrm A$ is invertible and, thus, the unique least-squares solution is

$$\hat{\mathrm x} := (\mathrm A^{\top} \mathrm A)^{-1} \mathrm A^{\top} \mathrm b$$

Consider now the augmented linear system

$$\begin{bmatrix} \mathrm A\\ \mathrm C \mathrm A\end{bmatrix} \mathrm x = \begin{bmatrix} \mathrm b\\ \mathrm C \mathrm b\end{bmatrix}$$

where $\mathrm C \in \mathbb R^{p \times m}$. We append $p$ equations to the original linear system, $\mathrm A \mathrm x = \mathrm b$, and each of these $p$ equations is a linear combination of the equations of the original linear system. The normal equations for the augmented linear system are

$$\begin{bmatrix} \mathrm A\\ \mathrm C \mathrm A\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A\\ \mathrm C \mathrm A\end{bmatrix} \mathrm x = \begin{bmatrix} \mathrm A\\ \mathrm C \mathrm A\end{bmatrix}^{\top} \begin{bmatrix} \mathrm b\\ \mathrm C \mathrm b\end{bmatrix}$$

which yields

$$\mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm A \mathrm x = \mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm b$$

Note that $\mathrm I_m + \mathrm C^{\top} \mathrm C$ is positive definite. If $\mathrm A$ has full column rank, then matrix $\mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm A$ is invertible and the unique least-squares solution for the augmented system is

$$\boxed{\hat{\mathrm x}_{\text{aug}} = \left( \mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm A \right)^{-1} \mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm b}$$

If the original linear system is consistent, i.e., $\mathrm A \hat{\mathrm x} = \mathrm b$, then

$$\hat{\mathrm x}_{\text{aug}} = \left( \mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm A \right)^{-1} \mathrm A^{\top} ( \mathrm I_m + \mathrm C^{\top} \mathrm C ) \, \mathrm A \hat{\mathrm x} = \hat{\mathrm x}$$

In words, if the original linear system is consistent, then the least-squares solutions of the original and augmented linear systems are the same.

---

$\boxed{\mathrm C = \gamma \mathrm I_m}$

If $\mathrm C = \gamma \mathrm I_m$, then

$$\mathrm I_m + \mathrm C^{\top} \mathrm C = (1+\gamma^2) \mathrm I_m$$

and the normal equations for the original and for the augmented linear systems are the same. Thus, the least-squares solutions for the original and for the augmented linear systems are also the same, whether the original linear system is consistent or not.