I am trying to approximate a square matrix $A \in \mathbb{R}^{n \times n}$ using the following matrix factorization

$$A \approx \hat{A} = Z \Lambda^{-1}Z^T$$

where $\Lambda=\text{diag}(Z^T \mathbb{1})$ and $Z$ is sparse. I would like to use stochastic gradient descent (SGD) in order to achieve that

$$\arg \underset{\hat{A}}{\min} \| A - \hat{A} \|$$

So, basically, I would compute some entries of $A$ (because $A$ is a huge matrix) and use these to factorize the matrix. But I am not very sure about the way to do it.

  • $\begingroup$ Is $A$ symmetric? Note that $\hat A$ is. Which matrix norm are you using? $\endgroup$ – Rodrigo de Azevedo Nov 24 '16 at 9:50
  • 1
    $\begingroup$ Yes $A$ is symmetric and the norm is spectral. $\endgroup$ – zunder Nov 24 '16 at 11:01
  • $\begingroup$ Where does this problem come from? What is the context? $\endgroup$ – Rodrigo de Azevedo Dec 1 '16 at 7:52
  • $\begingroup$ How do you want to enforce sparsity on Z? Are there extra penalty terms or constraints you haven't mentioned? $\endgroup$ – user20160 Sep 22 '17 at 18:14

The basic algorithm goes like this:

  1. Start with randomly initialized values of $Z$ and $\Lambda^{-1}$
  2. Go through each value $A_{ij}$
  3. Compute the gradient of $||A_{ij} - \hat{A}_{ij}||$
  4. Update the parameters $Z, Z^T$ and $\Lambda^{-1}$ in the direction of the gradient using a step size $\eta$. It's a hyper-parameter and needs to be learned using cross validation. $Z_i = Z_i - \nabla(||A_{ij} - (Z_{ij}^2 \times \Lambda_{jj} \times Z_i)||)$

In step 3 you may want to add regularization to prevent overfitting. Take a look at the pseudo code on Wikipedia.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.