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?

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.
