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).
