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.
As you said SVD can be used to factorize a full matrix without missing value. For sparse matrices we minimize the least square problem to get vector representing latent factors of an item 'qi' and a user 'pu'. You can start with some random values for the above latent factors and update them to get factors that minimizes the least square problem. This is your simple SVD in context with recommender system. SVD++ improves things over SVD by involving user implicit feedback which is termed as 'yi' and this helps you to characterize users based on set of items that they have rated.