Question: I have a sparse matrix. There is lots of missing data. Hence, I can't use SVD naively. 

I read Koren's SVD++ paper. I'm confused as to how the $q\_i$ and $p\_u$ vectors are determined. $q\_i^Tp\_u$ is supposed to capture the interactions between user $u$
and item $i$ (plus some biases). I just don't see how to calculate what $q\_i$ and $p\_u$ are supposed to be. The most natural things would be to use SVD but you can't since it has missing data.

Answer: 
The SVD theory is only used for motivation. In reality, SVD is not defined for a sparse matrix. For netflix there is less than 1% fille data so this tends to be an issue.

You are right that qi and pu are user and item matrices. He then uses gradient descent to solve them as a cost function.
In this problem matrix factorization model maps both users and items to a joint latent factor space of f dimensions. $q\_i$ and $p\_u$ are the latent factors in this context. Here problem is to estimate the values of $q\_i$ and $p\_u$ so that the the interaction of $q\_i$ and $p\_u$ i.e. $q\_i^Tp\_u$ can approximate the same rating matrix for the known data instances. Remaining missing values will automatically be imputed with the model.