Stochastic gradient descent and different approaches
I think you're actually asking two separate questions: 1) What is stochastic gradient descent (SGD)? and 2) how do I find the matrices $P$ and $Q$ in the matrix factorization of $M$?

For question 1, I don't think either of your explanations is correct. (Explanation 2 sounds to me like normal (batch) gradient descent, although I found your description a little confusing.)

Regardless, both the Wikipedia article and Chapter 5 of the Deep Learning book provides good explanations of SGD. In many machine learning problems, the loss function, $L$ can be decomposed as the sum of losses for individual training examples:

\begin{equation}
L(x, y; \theta) = \sum\limits_{i=1}^{m} L(x^{(i)}, y^{(i)}; \theta)
\end{equation}

Therefore, in normal gradient descent, the number of terms in the gradient scales with the number of training examples, $m$. Computing this term can be very costly as $m$ grows large. In stochastic gradient descent, we instead approximate the gradient by using a "mini-batch" of samples to compute it. So, instead of 

\begin{equation}
\nabla_{\theta} L(x, y; \theta) = \sum\limits_{i=1}^{m} \nabla_{\theta} L(x^{(i)}, y^{(i)}; \theta)
\end{equation}

we use 

\begin{equation}
\nabla_{\theta} L(x, y; \theta) \approx \sum\limits_{i=1}^{m_{mini}} \nabla_{\theta} L(x^{(i)}, y^{(i)}; \theta)
\end{equation}

where $m_{mini} \ll m$. The key point is that, when running SGD, we randomly shuffle the training examples and iterate through different minibatches during training. So, SGD is not equivalent to normal (batch) gradient descent for a smaller training set. In SGD, we train on all of the training examples, but it just takes us $m/m_{mini}$ iterations to get there. For instance, if $m_{mini} = 1$, and we took $m$ SGD steps, each step would correspond to using a single training example to approximate the gradient, and all $m$ steps would involve using a different training example.

For question 2, solving for the parameters in matrix factorization is usually done via alternating least squares (ALS) or SGD. Here's an excellent blog post explaining how both techniques work in the context of matrix factorization. The post is too long to summarize, but the author carefully and slowly derives all of the relevant equations from scratch, so I recommend you read it!