2
$\begingroup$

I'm a newbie at this forum, so I hope, that this question is not so silly.

Let's have some filter $F$, which is a linear combination, thus $F = \sum_{i=0}^{i=N}\alpha_ib_i$, where $\alpha_i$ are coefficients and $b_i$ are binary box functions. This decomposition is obtained by OOMP, however it is not important.

I've got the following problem: I need to normalize this filter so, that $L^2$ norm is equal to 1. I know, how to normalize $F$ (subtract DC component and compute $\frac{F}{\|F\|}$), however I need to normalize the linear combination with following constraint - recompute just coefficients $\alpha_i$, binary boxes $b_i$ can't be changed.

Thank you for your help.

  • 0
    Exactly, just $\alpha_i$. OOMP (optimal orthogonal matching pursuit) is a technique, how to select atoms from overcomplete dictionary (in this case, created by binary box functions) that make best approximation of some function. However, it is not important if you get this combination by OOMP, or by some other method. Important is, how to normalize it...2011-06-29

2 Answers 2

0

I tried to google for OOMP and I only got two hits. The first was for this page and the other for a paper on computer vision. I tried to skim that article, but probably I still have serious misunderstandings. Anyway, the problem I have in mind is the following. Using a 1-dimensional space to keep it simple. Assume that the domain is the interval $[0,9]$, and that the OOMP output is $f=1*\chi_{[1,2]}+2*\chi_{[4,8]}$, [Edit] in other words, there are two boxes: the interval $[1,2]$ and the interval $[4,8]$. [/Edit] This has a mean value of 1. I first assumed that removing the DC component amounts to subtracting the constant 1 from this function, but that would give us a function $f-1=-1*\chi_{[0,1)}-1*\chi_{(2,4)}+1*\chi_{[4,8]}-1*\chi_{(8,9]}$ and we necessarily create new boxes while doing that, because wherever the value was zero, there is a now a -1.

A way of getting a zero mean function out of this without modifying the set of boxes would be to subtract the mean of the restriction of $f$ to the union of the boxes. Here the union of boxes has measure 5 and the average of $f$ restricted to the union is $9/5$. So, if we do this subtraction business we get $ f-\frac95\,\chi_{[1,2]\cup[4,8]}=-\frac45\,\chi_{[1,2]}+\frac15\,\chi_{[4,8]}. $ The reason I think that this latter way of killing the DC-component is bad is that this changes the relative order of the components. The OOMP output marked the box $[1,2]$ as having something above the 'background'. If we subtract a constant only in the union of the boxes, then this box gets a negative sign indicating a level below the background. This is what I meant by saying that the quality of the approximation is now worse: In the computer vision paper the two boxes could in function $f$ mean that those two regions are both noted for being lighter than the surroundings. If the DC-component is removed by subtracting a constant function with support = the union of the boxes, then after this subtraction one of the original lighter regions is now hit with a negative number, and would be interpreted as darker than the surroundings. Ideally we might want the box generation algorithm itself to mark off both darker and lighter regions.

Here's the general formula that I used in the striked example (the latter, `suspicious' version, where no changes to the boxes are done). Let $\chi_{E_i}$ be the characteristic function of box $b_i$. Then the integral of $f$ over the union of the boxes is $\int f=\sum_i \alpha_i m(E_i),$ where $m(E_i)$ is the measure of the box $b_i$. A weighted measure of the union (=overlapping counted many times) is $m=\sum_i m(E_i)$. Then the function $ \tilde{f}=\sum_i(\alpha_i-\frac{\int f}m)b_i $ has zero mean. This you can then normalize to have unit $L^2$-norm in the usual way. Note you need to first replace $f$ with $\tilde{f}$ and then normalize. Not the other way around, because the $L^2$-norm goes down, when passing from $f$ to $\tilde{f}$. OTOH scaling the norm scales the mean value, so it won't reproduce a DC-component, if one didn't exist.

If you can spare the cycles, try this, and see if the results are ok. In the image-processing application the DC-component is a general grey level value, and you would have to take that into account outside the boxes also. Your application is hopefully very different.

  • 0
    Glad to hear that! I'm still a bit concerned about the possible distortion of your signals relative to the 'background' level outside the union of the boxes. Another potential problem may be that the intersections of boxes get a double hit with this formula, and that may further distort your signal. Please keep me posted! The system things we're chatting, so you may consider using e-mail:-) If you run into any anomalies while using this formula, then something else will be needed.2011-07-02
0

Supoose that the $\alpha$'s are real. Let $b_i=I_{E_i}$ (characteristic function) be the boxes. Let $|\cdot|$ denote the Lebesgue measure. Suppose $\alpha_1$ can be adjusted. Note that \begin{eqnarray}\|F\|^2&=&\sum_i\sum_j \alpha_i\alpha_j |E_i\cap E_j|\ &=& |E_1|\alpha_1^2+2\alpha_1\sum_{j=1}^N\alpha_j|E_i\cap E_j|+\sum_{i\not=1}\sum_{j\not=1} \alpha_i\alpha_j |E_i\cap E_j|.\end{eqnarray} Then using $t=\alpha_1$, $\|F\|^2$ has the form $f(t)=at^2+bt+c$ with $a>0$. So your problem is solvable if and only if $\min f\le 1$. For example, if $b=0$ (which happens if box $b_1$ is disjoint from the other boxes) and $c>1$, then $\|F\|$ cannot be normalized to $1$ by adjusting $\alpha_1$ alone. So it just depends on the interaction of the terms in your filter. If it can be done, the solution is the zero of a simple quadratic.

  • 0
    Exactly, you took the harder way :) however, thank you for your help... it seems that there was some matlab stuff again... :/ btw may I have one more question? how should I remove the DC component of $F$ (mean) from $\alpha$'s coefficients? I mean $F - mean(F) = \sum\alpha_ib_i - mean(F) = \sum (\alpha_i - ???)b_i$2011-06-30