I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone tell me how exactly is L1 sampling performed on edges of a graph.

To be more precise with my query, Should we vectorize the indices of the graph and then apply L1 sampling on the sub vectors and perform sparse recovery?(correct me if I am wrong) or is there a better way?

  • 1
    $\begingroup$ What is L1 sampling? $\endgroup$ – Yuval Filmus Jul 29 '18 at 10:53
  • $\begingroup$ dimacs.rutgers.edu/~graham/pubs/papers/l0journal.pdf - I was following this paper to understand l1 sampling. According to this paper, it is a sampling techniques used to sample near-uniformly ,from the support set of a dynamic multiset, and I was using sparsification algorithm in this paper - people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf (page 10) $\endgroup$ – sindhuja Jul 29 '18 at 11:22
  • $\begingroup$ It seems that edges should be sampled proportional to their weight. If the total weight is $W$, then an edge with weight $w$ should be sampled with probability $w/W$. $\endgroup$ – Yuval Filmus Jul 29 '18 at 11:54
  • $\begingroup$ Okay, I see that, but, this sampling technique is performed on stream of data, not necessarily graph streams(correct me if I am wrong). Then would the stream on which we implement the L1 sampling contain indexes of the edges? $\endgroup$ – sindhuja Jul 29 '18 at 13:31
  • $\begingroup$ Yes, that's an equivalent formulation, though I disagree that you can only sample from streams. Pollsters sample voters from the population without using any streams of any sort. $\endgroup$ – Yuval Filmus Jul 29 '18 at 15:13

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.