2
$\begingroup$

I am having trouble simulating a matrix which is low rank and sparse (sparse along both rows and columns). One way to simulate a low-rank matrix is by generating a random matrix, then taking SVD and then taking only a few components to generate a new matrix with a low rank. But, I don't know how to simulate a matrix which is also sparse at the same time low rank. Is there a way to simulate a matrix having $k$ rank, and sparsity between $x$% and $y$%.

Edit 1: Using this simulation I want to test this https://math.stackexchange.com/questions/2916150/rank-comparison-for-different-low-rank-approximations question

$\endgroup$
  • $\begingroup$ You need a lot more information. Is the matrix sparse along the rows, the columns or both? Is there a distribution of non zeroes you want to model? $\endgroup$ – ReneBt Sep 26 '18 at 22:03
  • $\begingroup$ A really sparse matrix will automatically have a low rank. As @ReneBt indicates, you need to be more specific about what you're trying to do. In particular, what operation is implied by "make it sparse"? $\endgroup$ – whuber Sep 26 '18 at 22:37
  • $\begingroup$ @ReneBt I just want the matrix to be sparse, there should not be necessarily a distribution of non-zeros $\endgroup$ – Dushyant Sahoo Sep 27 '18 at 16:59
  • $\begingroup$ @whuber Edited the question $\endgroup$ – Dushyant Sahoo Sep 27 '18 at 17:00
  • 2
    $\begingroup$ Re the edit: that question contains the elements of an appropriate answer: generate the $b_i$ as sparse random vectors. For non-square matrices an obvious generalization of the form $\sum b_i c_i^\prime,$ for sparse vectors $b_i$ and $c_i,$ will work. You still have tremendous flexibility in determining the distributions of these vectors. $\endgroup$ – whuber Sep 28 '18 at 19:40
0
$\begingroup$

If you want a sparse matrix you can generate one in Python.

import numpy as np
import matplotlib.pyplot as plt
import math
from scipy.sparse import random
from scipy.stats import rv_continuous
from scipy import sparse, svds

class CustomDistribution(rv_continuous):
    def _rvs(self, *args, **kwargs):
        return self._random_state.randn(*self._size)
X = CustomDistribution(seed=2906)
Y = X()  # get a frozen version of the distribution
S = random(10, 10, density=0.05, random_state=2906, data_rvs=Y.rvs)
S.A

u, s, vt = svds(S, k=2) 

this would generate the first k singular values. You can form a low-rank approximation that way.

It should be noted that is simply a $10 \times 10$ matrix with given density $ 0.05$ and $k=2$

You could technically make the sparsity pattern how you like it. It looks fairly sparse to me....e.g

u, s, vt = svds(S, k=2) 
s1 = np.diag(s)
A1 = np.dot(np.dot(u,s1),vt)
m = sparse.coo_matrix(A1)
plt.spy(m)

enter image description here

looks sparse to me

Technically everything in that matrix was below $1e-16$ so we can thresh hold it and let's look at rank $k=4$

   u, s, vt = svds(S, k=4) 
s1 = np.diag(s)
A1 = np.dot(np.dot(u,s1),vt)
# thresh hold for machine precision
epsilon  = math.exp(1e-14)-1
# filter them out
A1[A1 < epsilon ] =0
m = sparse.coo_matrix(A1)
plt.spy(m)

enter image description here

$\endgroup$
  • $\begingroup$ If you first generate a sparse matrix and then take a low-rank approximation, then it is not necessary that the low-rank approximation would be sparse. I want to get a matrix which is low-rank as well as sparse. $\endgroup$ – Dushyant Sahoo Sep 28 '18 at 19:05
  • $\begingroup$ I edited it with a visualization of the sparsity structure. $\endgroup$ – user28896 Sep 28 '18 at 19:18
  • $\begingroup$ note that at $k=2$ everything was machine precision. Now look at the update sparse matrix $\endgroup$ – user28896 Sep 28 '18 at 20:07

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.