I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$. The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ok, so we need at most $s$ nonzeros in $B$.

The probability of entry $A_{kl}$ being chosen is $p_{ij} = \frac{A_{ij}^2}{\sum_{k, l} A_{kl}^2}$, in which, $k$ and $l$ go through all the matrix entries. I have this algorithm in mind so far:

  1. generate a random number $rand$ such that $0\le rand \le 1$.
  2. if $(rand < p_{11}) \implies$ add $A_{11}$ to $B$.
  3. go to the next entry of $A$ and repeat from step $1$ until $s$ entries are chosen.

If I go through all entries of $A$ once, on average how many entries will be chosen? In other words, how many times I should go through entries of $A$ to have $s$ entries chosen?

I want to change the probability $p_{ij}$ so by going through entries of $A$ once, all $s$ entries are chosen.


Your Answer

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

Browse other questions tagged or ask your own question.