Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Your question is somewhat vague. Are you defining the function $f(x)$ to be $\min(0,x)$, or is $f(x)$ a function that is already defined and you want to impose the constraint that $f(x)=\min(0,x)$? If you're defining $f(x)$ to be $\min(0,x)$, then how else does $f(x)$ appear in your problem? Does it appear in other constraints? Does it appear in the objective function?
My oops- I had thought there was an $O(n^2)$ way to get the inverse of a lower triangular matrix but my memory was faulty. Sorry about that. For the product form cholesky factorization, look at the 2005 paper by Goldfard and Scheinberg, "Product-form Cholesky factorization in interior point methods for second-order cone programming" and follow references back from there. See portal.acm.org/citation.cfm?id=1058105
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.
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.
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.
You've stated that your signal is discrete, which is hugely important. How long are your signals- hundreds of samples? thousands of samples? millions of samples?
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.
You haven't been specific about what you mean by $|w-w'|$. Is this $ | w - w' | = \sum_{i=1}^{n} | w_{i}-w'_{i} | $ or $ | w - w' | = \max_{i=1, 2, \ldots, n} | w_{i}-w'_{i} | $ or something else?
No, this doesn't really do it. The problem here is that your Haar wavelets $\Psi_{n,k}$ have fixed scaling and shifts. The original poster wants to use a limited number of functions but adjust the scaling factors and shifts.
