Given two strings S and T of same length, it is trivial to compare if S=T. If S were of length n, T were of length m, n > m, we can ask whether T appears as a substring of S, that is, T=S[i,i+m-1], for some i. Then, there are potentially O(n-m) substrings of S to be compared to T, and the problem is now the non-trivial, much-studied string matching problem. In this example and elsewhere, switching from strings to substrings normally makes problems interesting.
Let me propose a similar extension for the recently-solved compressed sensing problem which is: given a signal S[1,m] that is k-sparse in some m-dimensional basis, find approximate reconstruction of S with klog (n/k) linear measurements. An extension is, given an m-dimensional basis and S[1,n] where each S[i,i+m-1] is k-sparse in that basis, find an approximate reconstruction of S faster than it takes to solving O(n-m) instances of the basic compressed sensing problem independently and collating a suitable approximation to S, or is better approximation to S than solving O(n/m) nonoverlapping instances of the basic compressed sensing problem.
To be honest, I am doing
seat-of-the-pants research here. I haven't figured out what class of S's satisfy the conditions above, what is a suitable definition of approximate reconstruction of such S's, where problems of this type arise. That doesn't stop me from saying problems of these sorts can be solved using random set of linear measurements of dimension m, FFTs, suitable sublinear reconstruction algorithms, and (all standard fare so far, but now the handwave) some way of taking consensus from the O(n-m) sets of O(k polylog) basis vectors to get O(nk polylog) time approximation to S. Hope someone proves me right or wrong, they can take all the credit of course because almost certainly they have to formulate the problem more precisely (provided they too are not flying by the seat-of-the-pants).
