MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm wondering if compressed sensing can be applied to a problem I have in the way I describe, and also whether it should be applied to this problem (or whether it's simply the wrong tool).

I have a large network and plenty of data on each node. I want to find a set of communities that explain most data similarity and track these communities over time. In a compressed sensing formulation this amounts to the following:

-My graph's representation basis is a weighted set of communities, where each community is a subset of the set of all nodes (candidate communities can be narrowed down to a tractable number rather easily)

-Different feature measures (e.g. bigrams, topic profiles) serve as my sensing basis, with correlations between community membership and features serving as the coefficients of my measurement matrix. The big assumptions, that my feature measurements have the Restricted Isometry Property, that similarity is incoherent with community, and that similarity is a linear combination of community, are all almost certainly incorrect, however they seem plausible approximations to within (possibly significant) noise.

Ideally, I can use this strategy to describe my network as a collection of communities and to track over time the prominence of these communities. I wonder, however, if there isn't some straightforward bayesian method that I'm overlooking.

Misc Questions about Compressed Sensing:

i) If my measurements are not linear combinations of my representation basis, but at least convex, then can I still usefully use compressed sensing? Edit: In the above case, for instance, the generally accepted submodularity property of networks means that a node's membership in additional communities that correlate positively with a feature have reduced effect. In this particular case it might be best to transform everything to logs, but in general this option might not be viable.

ii) What is the meaning of the dual of basis pursuit?

iii) How does one avoid basis mismatch in general? You choose your representation basis elements beforehand, so how do you make sure they're capable of representation?

Edit iv) If your measurements are naturally represented as vectors, rather than scalars, is there any way to represent this other than counting each component of the vector as a separate measurement (though I suppose this works fine in general, if you have enough information about each component and everything is linear).

share|cite|improve this question
I'm going to try to answer Miscellaneous Question (ii) myself. If Basis pursuit is viewed as an attempt to find an exact "Covering" of representation bases (With minimized sum of coefficients) given the sampling bases results, then its dual is an attempt to maximize the weighted (and unrestricted) coefficients of the sampling bases given restrictions on the representation bases. If the representation bases are wavelets, and the sampling bases are masks, then basis pursuit's dual is weighted maximum mask "packing" given that all wavelet coefficients must be less than 1. – DoubleJay Jul 19 '10 at 3:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.