I was trying to understand better when we can learn a unique parameter for linear regression and how much data is required to get one.
Say that we want to learn a parameter $\theta$ such that empirical risk is minimized $R_n(\theta)$. For that we want:
\begin{align} \bigtriangledown R_{n}( \theta )_{\theta = \hat{\theta}} &= 0 \\ \bigtriangledown\frac{1}{n} \sum^n_{t=1} (y^{(t)} - \theta \cdot x^{(t)}) &= \frac{1}{n}\sum^n_{t=1}-y^{(t)}x^{(t)} + \frac{1}{n} \sum^n_{t=1}x^{(t)} {x^{(t)}}^{T}\theta \end{align}
If we let $b = \frac{1}{n}\sum^n_{t=1}y^{(t)}x^{(t)}$, and $A = \frac{1}{n} \sum^n_{t=1}x^{(t)} {x^{(t)}}^{T}\theta$, then we can re-write it as:
\begin{align} -b + A \hat{\theta} &= 0 \\ A \hat{\theta} &= b \end{align}
or also more commonly known as:
\begin{align} b &= \frac{1}{n}x^{T}y \\ A &=\frac{1}{n}X^{T}X \\ X^{T}X \hat{\theta} &= X^{T}y \end{align}
But it was not clear to me what conditions we required for $A$ or $X$ so that $A$ was invertible. It obvious that $A$ should span the $R^d$ where $d$ is the dimensionality of the data, but how does that translate how the training data should span that subspace? I guess I am specifically unsure about when $A$ is invertible in relation to $X^T X$.
This is mainly a linear algebra question, however, since I posted this in the context of machine learning too, it would nice to get a response that explains what conditions we need to have of the training points such that such that $X^TX$ is invertible. i.e what conditions we need on the rows of X such that $X^TX$ is invertible.
(Also, I am interested on an answer that is informative, but if it comes with a proof of the claims that will make me most happy)
