Timeline for Decomposing a discrete signal into a sum of rectangle functions
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2011 at 11:26 | comment | added | rodrigob | For a large enough problem, the second work around is guaranteed to be slower than the second one ($O(m^2)$ versus $O(m)$ in the 1D case). However, given the architecture of modern computers, it is unclear if for the size of my specific problem the first work around is more efficient than the second one. I guess only experiments will tell... | |
| Apr 28, 2011 at 11:22 | comment | added | rodrigob | Another work around I found is based on the specific properties of the problem. If instead of solving $\sum_i\ \left| w_i - w_i'\right|$, I solve $\sum_i\ \left( w_i - w_i'\right)^2$, then it turns out that I can find the maximum inner product by doing only two memory reads, one multiplication and one division for each basis. In this approach the complexity explodes (in big O notation), but the cost of each step is very small (four operations). | |
| Apr 28, 2011 at 11:17 | comment | added | rodrigob | One work around (the one mentioned in the question) is to fix a value $a_i$, then the search of the maximum inner product can be transformed to a subarray search (which is a known problem with efficient solution). By brute force exploring the range of $a_i$ values we can expect to have a "not too bad solution". | |
| Apr 28, 2011 at 11:16 | comment | added | rodrigob | Yes the problem is 2D but I presented it as 1D to make things simpler. Indeed the matching pursuit trail seems interesting. Up to now I have figured out two ways to solve the presented problem (one of them mentioned in the question), and both are similar to a matching pursuit formulation. The key point is not computing the inner product between the residual and the all the bases, since the enumeration of bases will "explode". This step must be replaced by something else. Right now I have two alternatives (see next comments). | |
| Apr 27, 2011 at 20:54 | comment | added | Brian Borchers | It also occurs to me that since your signals are actually 2D, you need to be using 2D basis functions- this would greatly expand the dimensions of the problem. That being the case, I've got nothing better to offer than the iterative scheme mentioned in my previous comment. | |
| Apr 27, 2011 at 20:51 | comment | added | Brian Borchers | Simple iterative schemes such as "orthogonal matching pursuit" are often used on very large problems in compressive sensing. Here, you would start by finding the one rectangle that does the most to reduce $\| w - w' \|_{1}$, then recursively repeat this process on what's left until you've got as many terms as you're willing to use. This won't give you a solution that is necessarily optimal, but it might work well in practice. | |
| Apr 27, 2011 at 20:48 | comment | added | Brian Borchers | If your problems are that large, than the integer programming formulation is out of the question. However, in compressive sensing practice, solving problems with $~ 10^6$ variables is not at all uncommon. First note that you don't necessarily need to be able to store the $A$ matrix explicitly to solve this problem- there are iterative methods that only need the ability to do matrix-vector multiplies with $A$ and $A^{T}$. Even if you did have to store $A$ explicitly, general purpose LP solvers are often used to solve LP's with millions of variables. So, this may not be out of reach. | |
| Apr 27, 2011 at 18:31 | comment | added | rodrigob | This proposal corresponds to path 2 in my question. I though of this, however in my setup $A$ in too big (w is actually 2D, so the entries of $A$ grow as $n^4$, in practice the columns of $A$ will be $\sim10^{6}$). Is it there a way to solve this without explicitly computing $A$ ? | |
| Apr 27, 2011 at 17:20 | comment | added | Brian Borchers | Although I didn't include this in my answer, it's easy to translate the $\| w -w' \|_{1}$ objective and inequalities involving $| x_{i} |$ into linear programming constraints- this is standard textbook material. | |
| Apr 27, 2011 at 17:14 | history | answered | Brian Borchers | CC BY-SA 3.0 |