Return to Question

Hello mathoverflow community !

I have a simple question that seems to have a non trivial answer.

Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar (rectangular) function $r(x)$

$$r(x)=\begin{cases} 1 & \mbox{if }0\leq x \leq 1; \\ 0 & \mbox{elsewhere} \end{cases}$$

I would like to find the coefficients $a_i,\ b_i,\ c_i $ of the sum

$$w' = \sum_{i=0}^{N}\ { a_i \cdot r\left(\frac{x}{b_i} - c_i\right)}$$

("sum of $N$ rectangles in any range and of any height") such as $\sum_i\ \left| w_i - w_i'\right|$ is minimized (for a given $N$).

This problem seems related to:

1. Discrete wavelet transform
2. $l_1$ regularized solution of an overdetermined linear system
3. Maximum subarray problem

However, to my understanding it does not fit any of these cases:

1. $r(x)$ is not a wavelet basis,
2. the problem cannot be solved (practically) as a linear system because the (finite) set of $a_i,\ b_i,\ c_i $ values is too large to compute explicitly,
3. Since $a_i$ is undefined, it does not fit as a maximum subarray problem.

Right now I have an approximate solution (iteratively solving the problem via maximum subarray formulation by brute force exploring a subset of possible $a_i$ values), however the idea of "decomposing a signal as a sum of rectangles" seems general enough to think that someone has already addressed it in the past.

Do any of you have a suggestion on how to tackle this problem ?

Has it already been solved in the past, by a method I am not aware of ?

Thank you very much for your answers.

Hello mathoverflow community !

I have a simple question that seems to have a non trivial answer.

Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar (rectangular) function $r(x)$

$$r(x)=\begin{cases} 1 & \mbox{if }0\leq x \leq 1; \\ 0 & \mbox{elsewhere} \end{cases}$$

I would like to find the coefficients $a_i,\ b_i,\ c_i $ of the sum

$$w' = \sum_{i=0}^{N}\ { a_i \cdot r\left(\frac{x}{b_i} - c_i\right)}$$

("sum of $N$ rectangles in any range and of any height") such as $\sum_i\ \left| w_i - w_i'\right|$ is minimized (for a given $N$).

This problem seems related to:

1. Discrete wavelet transform
2. $l_1$ regularized solution of an overdetermined linear system
3. Maximum subarray problem

However, to my understanding it does not fit any of these cases:

1. $r(x)$ is not a wavelet basis,
2. the problem cannot be solved (practically) as a linear system because the (finite) set of $a_i,\ b_i,\ c_i $ values is too large to compute explicitly (length of $w$ in the order of $10^4$),
3. Since $a_i$ is undefined, it does not fit as a maximum subarray problem.

Right now I have an approximate solution (iteratively solving the problem via maximum subarray formulation by brute force exploring a subset of possible $a_i$ values), however the idea of "decomposing a signal as a sum of rectangles" seems general enough to think that someone has already addressed it in the past.

Do any of you have a suggestion on how to tackle this problem ?

Has it already been solved in the past, by a method I am not aware of ?

Thank you very much for your answers.

Hello mathoverflow community !

I have a simple question that seems to have a non trivial answer.

Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar (rectangular) function $r(x)$

$$r(x)=\begin{cases} 1 & \mbox{if }0\leq x \leq 1; \\ 0 & \mbox{elsewhere} \end{cases}$$

I would like to find the coefficients $a_i,\ b_i,\ c_i $ of the sum

$$w' = \sum_{i=0}^{N}\ { a_i \cdot r\left(\frac{x}{b_i} - c_i\right)}$$

("sum of $N$ rectangles in any range and of any height") such as $\sum_i\ \left| w_i - w_i'\right|$ is minimized (for a given $N$).

This problem seems related to:

• Discrete wavelet transform
• $l_1$ regularized solution of an overdetermined linear system
• Maximum subarray problem

However, to my understanding it does not fit any of these cases:

• $r(x)$ is not a wavelet basis,
• the problem cannot be solved (practically) as a linear system because the (finite) set of $a_i,\ b_i,\ c_i $ values is too large to compute explicitly,
• Since $a_i$ is undefined, it does not fit as a maximum subarray problem.

Right now I have an approximate solution (iteratively solving the problem via maximum subarray formulation by brute force exploring a subset of possible $a_i$ values), however the idea of "decomposing a signal as a sum of rectangles" seems general enough to think that someone has already addressed it in the past.

Do any of you have a suggestion on how to tackle this problem ?

Has it already been solved in the past, by a method I am not aware of ?

Thank you very much for your answers.

Hello mathoverflow community !

I have a simple question that seems to have a non trivial answer.

Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar (rectangular) function $r(x)$

$$r(x)=\begin{cases} 1 & \mbox{if }0\leq x \leq 1; \\ 0 & \mbox{elsewhere} \end{cases}$$

I would like to find the coefficients $a_i,\ b_i,\ c_i $ of the sum

$$w' = \sum_{i=0}^{N}\ { a_i \cdot r\left(\frac{x}{b_i} - c_i\right)}$$

("sum of $N$ rectangles in any range and of any height") such as $\sum_i\ \left| w_i - w_i'\right|$ is minimized (for a given $N$).

This problem seems related to:

1. Discrete wavelet transform
2. $l_1$ regularized solution of an overdetermined linear system
3. Maximum subarray problem

However, to my understanding it does not fit any of these cases:

1. $r(x)$ is not a wavelet basis,
2. the problem cannot be solved (practically) as a linear system because the (finite) set of $a_i,\ b_i,\ c_i $ values is too large to compute explicitly,
3. Since $a_i$ is undefined, it does not fit as a maximum subarray problem.

Right now I have an approximate solution (iteratively solving the problem via maximum subarray formulation by brute force exploring a subset of possible $a_i$ values), however the idea of "decomposing a signal as a sum of rectangles" seems general enough to think that someone has already addressed it in the past.

Do any of you have a suggestion on how to tackle this problem ?

Has it already been solved in the past, by a method I am not aware of ?

Thank you very much for your answers.