# How to choose basis functions that contribute most efficiently per term to an approximation of an image f(x,y)?

GOAL:

I would like to approximate some positive, scalar function, $f(x,y) > 0$, on a 2D field of finite size i.e. $x=[a,b],y=[c,d]$

OBSTACLE:

I am familiar with the set of basis functions used in the Fourier series but using the Fourier series requires too many terms. Infinitely many:)

Instead, I desire to find a collection of functions that can be used to approximate $f(x,y)$ with a "finite" number of terms.

QUESTION:

How can I approximate $f(x,y)$ with a collection of functions $G(x)$ and $H(y)$ (see definition of $G$ and $H$ below), such that the number of elements in $G$ or $H$ is finite?

$$G(x) = [g_1(x)\ldots g_n(x)]\\ H(y) = [h_1(y)\ldots h_n(y)]$$

The elements in $G$ and $H$ do not have to be of the same form ($g_1(x)=\sin(nx),g_2(x)=\sin(mx)$)

EDIT:

I should clarify that $G(x)$ and $H(y)$ need to be combined in an inner product fashion i.e.

$$f(x,y) = < G(x),H(y) > = g_1(x)h_1(y) + g_2(x)h_2(y) + ... g_n(x)h_n(y)$$

• I'm not familiar with the word "frame" used in this context. Could you elaborate? – ElecEng2016 Dec 20 '15 at 22:05
• Ok, sorry. I just looked it up. I could settle with a frame as long as it is accurate enough in representing f(x,y) – ElecEng2016 Dec 20 '15 at 22:12
• I don't have enough reputation to change the displayed score. I have upvoted – ElecEng2016 May 26 '17 at 18:52

I do not understand why you need an infinite number of terms for a Fourier approxiimation. Yet, if you are looking for tools on non-discretized 2D data, I would suggest you to start with the concept of Matching pursuit of images. You take a dictionary of 2D atoms that is complete (could be complex exponentials, gaussian bumps). Then, you find the atom that best matches you data, subtract it with the necessary scale factor, and repeat.

You could also resort to anisotropic triangulations, but this would not suit your "need to be combined in an inner product fashion".

The quality of approximation could be evaluated over some classes for regular functions ($C^p$ smooth inside $C^q$ curves), and are related to properties of your dictionary. You might find some references in section 4.1.1. Matching pursuits from A panorama on multiscale geometric representations, Signal Processing, 2011, L. Jacques et al.

I do suspect that the inner-product constraint will limit the efficiency: optimal approximations in 1D do not extend generically in 2D.

• Thank you, that was a great answer. Also, I guess I assumed you need infinite terms for a Fourier series approximation because I was thinking of having the approximation exactly equal the function beinf approximated. – ElecEng2016 Dec 22 '15 at 19:00
• A digital image. It isn't exactly continuous but I thought it would be appropriate to present it as such since images are most often (null example might be some computer generated image) sampled analog phenomenon. – ElecEng2016 Dec 23 '15 at 23:08
• Great paper @LaurentDuval , wish I had found it a few years ago :( – geometrikal Feb 20 '16 at 2:48

Late response, but it may help others in the futrue: why not use a taylor or MacLaurin series expansion? Here is a handy calculator But the expansion for sin is well defined take a look at wikipedia

The taylor/maclaurin series gives approximations for equations about a specific point to approximate the functions true value. In fact this is actually how calculators/computers compute many complex functions (exponentials, sinusoids, logs, etc). Your terms would be Cx^n where n indicates the number of terms to include, C is a constant coefficient. More terms = more precision You can almost think of these as a fourier series where x^n closely mirrors e^jx and C is your coefficient. As Laurant mentioned, you don't need the entire infinite set to get an answer, using the most powerful terms will result in a signal that is close enough