# L1 sampling for sampling edges of a graph

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?

• What is L1 sampling? – Yuval Filmus Jul 29 '18 at 10:53
• 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) – sindhuja Jul 29 '18 at 11:22
• 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$. – Yuval Filmus Jul 29 '18 at 11:54
• 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? – sindhuja Jul 29 '18 at 13:31
• 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. – Yuval Filmus Jul 29 '18 at 15:13