What do you do in regression if $(X^\text{T} X)^{-1}$ does not exist? Assume we want to solve $X z=b$ for $z$ where $X$ is a non-square matrix and $z$ and $b$ are column vectors. In case the system is overdetermined, we have no solution and can look  for a solution which minimizes $||Xz-b||^2$. The solution is given by the pseudoinverse, so that $z^*=(X^T X)^{-1}X^Tb$.
My question is, what happens if $X^TX$ is not invertible? In a typical regression problem, where $X$ is the matrix with features on the columns and data points on the rows. Does the problem of $X^TX$ not being invertible ever occur in regression? If so, how is it solved?
 A: The matrix $X^\text{T} X$ is the Gramian matrix of the design matrix (assuming here that the design matrix has elements that are all real numbers).  If the Gram-determinant is zero (i.e., if $\text{det} (X^\text{T} X) = 0$) then the Gramian matrix is not invertible, which means that the design matrix has at least one column of values that can be constructed as a linear combination of the other columns.  When this occurs there are regression coefficients in the model that are non-identifiable and there are an infinite number of solutions for the estimated regression coefficients in the OLS/MLE problem in the regression model.
To fix this problem, we remove redundant explanatory variables from the model (corresponding to removing columns of the design matrix) until we get a design matrix that has a Gram-determinant that is non-zero.  We remove the excess explanatory variables because they are not giving any additional information in the model.  Once we have removed the excess explanatory variables and have a non-zero Gram-determinant for the design matrix, we can then estimate the coefficients of the reduced model and proceed as normal.
A: There are two common settings where the problem occurs in regression, and these are treated differently.
The first is when the number of columns $p$ of $X$ is greater than the number of rows $n$. In that case you can't do the regression, and you need some sort of dimension-reduction approach.  You might do subset selection or $L_1$-type penalisation (lasso) or shrinkage without dropping variables (ridge regression, mixed models) or just think about variables you are willing to drop.
The second is when you have just set up $X$ wrong and the solution is to fix it.  For example, if you have a $k$-level categorical variable and you set up $k$ indicator variables ('one-hot' encoding) then $X^TX$ will be singular and the solution is to change to an encoding by $k-1$ variables (just drop a variable to get treatment contrasts or switch to sum-to-zero contrasts or Helmert or whatever)
When $p$ is slightly less than $n$ and the data aren't recorded to very high precision, it's not that unusual to get get $X^TX$ singular, and that's basically like the $p>n$ setting.
It's fairly unusual to have $X^TX$ singular when $p\ll n$ and there isn't a simple and fixable symbolic issue with encoding. It's not impossible; it can happen; but it's unusual. It happened more a bit often in the Bad Old Days when we were all working with stone axes and 7-digit floating point.
