Linear Regression: Why use global basis functions instead of local basis functions I'm looking through an online course about machine learning and the first big topic is finding a model that approximates our data with linear regression. 
The model itself is linear function and we look for the coefficients of that linear function.
We introduce non-linearities that the data might have into our linear model by adding feature crosses.

For example, lets say we have two-dimensional features ($x_1, x_2$) and label them as $1$ if they are in the 2nd or 4th quadrant, 0 otherwise. A linear function $y(x_1, x_2) = b +m_1x_1+m_2x_2$ cannot approximate this. If we add $x_3 = x_1x_2$, we can find a model that represents that.

However, this is obviously a very artificial problem and not at representative to solve against any kind of data. In the end, we are trying to find a function $y$ that fits some data. This reminds me of solving differential equations numerically. And there we build the function $y$ as a sum of local basis functions $y(x) = \sum_i m_i\phi_i(x)$.

Why would we use global basis functions instead of local basis functions to introduce non-linearity into our linear machine learning model? Why don't we discretize our feature space and optimize on a linear function space?
I see a couple of parts to your question

Part 1


  Why would we use global basis functions instead of local basis
  functions to introduce non-linearity into our linear machine learning
  model?


Local (non-global) basis functions are used sometimes. For example, radial basis functions (RBF) are sometimes used as a basis in linear regression (see these lecture notes). 

However, often it matters that a model is interpretable and more complicated models are harder to interpret / draw certain conclusions from.  For example, imagine you're doing a controlled experiment, you may not care about "just" predicting some variable from (the variable you're manipulating + the variables you're controlling for).  But rather, how much of an effect your manipulation has on the output.

Part 2


  Why don't we discretize our feature space and optimize on a linear function space?


RBFs kind-of discretize feature space.  People don't usually literally discretized feature space because discrete optimization is much much more complicated than continuous optimization.