1

I have a set of functions $f_i,\, i=1,2,\ldots,n$ defined on an interval $[a,b]$, and a function $F$ also defined on $[a,b]$. I would like to project F on a subset of functions $f_i$ so that the number of $f_i$ used to represent $F$ is minimum, but $\|F-\sum\limits^k_{i=1}f_iw_i\|\rightarrow0$, where $w_i$ are some weights. Any help on this problem or a reference leading to its solution is very welcome.

Thank you.

Karla

Karla
  • 71
  • 1
    What do you mean when you say "but $|F-\sum\limits^k_{i=1}f_iw_i|\rightarrow0$"? – littleO Jan 22 '15 at 09:49
  • I just wanted to say that the difference between $F$ and its projection is small for the minimum number of $f_i$, which is denoted by $k$. – Karla Jan 22 '15 at 10:16
  • The problem can also be reformulated as a function expansion problem: expand $F$ into a sum $\sum\limits^k_{i=1}f_iw_i$ so that $|F-\sum\limits^k_{i=1}f_iw_i|\rightarrow0$. – Karla Jan 22 '15 at 12:29

1 Answers1

0

One idea could be to sample the functions $F$ and $f_i$ at a bunch of points in the interval $[a,b]$, obtaining vectors $G$ and $g_i$. Then minimize $\| w \|_1 + \alpha \| G - \sum_{i=1}^n g_i w_i \|$ with respect to $w$. (Here $\alpha > 0$ is a parameter you can tune.) That's a convex problem so it could be solved efficiently.

A key point is that by penalizing the $1$-norm of $w$ we encourage $w$ to be sparse. So most of the components of the optimal $w$ will be equal to $0$.

littleO
  • 51,938
  • I've tried the idea with fminsearch in MATLAB, but the result is poor. – Karla Jan 22 '15 at 15:28
  • @Karla You could try solving the optimization problem using CVX, which might do better. How many sample points did you use? Did you try many different values of $\alpha$? What about the results is poor? – littleO Jan 23 '15 at 03:54
  • I used 243 sample points and different values of $\alpha$ but it didn't help. The poor results mean a large value of $|F-\sum\limits^n_{i=1}f_iw_i|$, which is far a way from being optimal. Perhaps, I should try CVX. – Karla Jan 23 '15 at 09:02
  • What's your value of $n$? – littleO Jan 23 '15 at 09:06
  • $n=243$ and the length of the vectors $G$ and $g_i$ is also 243. – Karla Jan 23 '15 at 09:11
  • I see. Is $|G - \sum_{i=1}^n g_i w_i |$ small, at least? When $\alpha$ is large, if the optimization problem is being solved correctly, then $|G - \sum_{i=1}^n g_i w_i |$ should be nearly $0$. – littleO Jan 23 '15 at 10:30
  • $| G - \sum_{i=1}^n g_i w_i |$ is around several hundreds. – Karla Jan 23 '15 at 11:25
  • Assuming the vectors $g_i$ are linearly independent, you should be able to pick the $w_i$ so that $G - \sum_{i=1}^n g_i w_i$ is exactly $0$. As a sanity check, you could try just minimizing $G - \sum_{i=1}^n g_i w_i$ by itself, and check that the minimum value is $0$. Also, you could try putting the vectors $g_i$ into the columns of a matrix $M$. Let w = M\G ; (using Matlab notation), and check that $G - \sum_{i=1}^n g_i w_i$ is $0$. – littleO Jan 23 '15 at 11:33
  • Of course, it is 0, but I'd like to have the minimum number of $g_i$. – Karla Jan 23 '15 at 11:37
  • Yes, just a sanity check. I'd be interested in seeing the functions $F$ and $f_i$ explicitly, if it's not hard to write them. Where does this problem come from, out of curiosity? – littleO Jan 23 '15 at 20:30
  • The problem is that I have neither $F$ nor $f_i$ in an explicit form. They are just a bunch of numbers. I can send you the data if you'd like. – Karla Jan 24 '15 at 08:37