2
$\begingroup$

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.

$\endgroup$

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.