# Approximating the basis of a specific function

We are given a continuous function $$g: A \to B$$, where $$A, B$$ are compact subsets of $$\mathbb{R}$$.

We define a function $$f(x) := g(b_1x)+g(b_2x)+...+ g(b_mx)$$, where $$b_i < 1$$ and $$b_ix$$ is a scalar multiplication of $$x$$ by $$b_i$$. (Actually $$b_i$$ are much less than $$1$$).

I want to prove that we can approximate $$f(x)$$ with certain $$k$$ functions $$[g(b_{j_1}x),g(b_{j_2}x),...g(b_{j_k}x)]$$ from the original set, where $$k$$ is very small compared to $$m$$.

Here is an outline why I believe this is true:

By Stone-Weierstrass theorem, $$g(x)$$ can be approximated as close as we like by polynomials;

$$g(x) \approx a_0+ a_1x+a_2x^2+...+a_nx^n$$

Then,

$$g(b_1x) \approx a_0 + a_1(b_1)x+a_2(b_1)^2x^2+...+a_n(b_1)^nx^n$$

$$g(b_2x) \approx a_0 + a_1(b_2)x+a_2(b_2)^2x^2+...+a_n(b_2)^nx^n$$

$$\vdots$$

$$g(b_mx) \approx a_0+a_1(b_m)x+a_2(b_m)^2x^2+...+a_n(b_m)^nx^n$$

Then,

$$f(x) \approx a_0\sum_{i=1}^m 1 + a_1x\sum_{i=1}^mb_i + ... + a_nx^n\sum_{i=1}^m(b_i)^n$$

If we represent $$f(x)$$ and $$g(b_ix)$$ as column vectors:

$$\begin{bmatrix} a_0\sum_{i=1}^m 1 \\ a_1\sum_{i=1}^mb_i \\ ... \\ a_n\sum_{i=1}^m(b_i)^n \end{bmatrix}$$ $$\begin{bmatrix} a_0 & a_0 & ...& a_0 \\ a_1b_1 & a_1b_2 & ... & a_1b_m\\ ... & ... & ... & ... \\ a_n(b_1)^n & a_n(b_2)^n &... & a_n(b_m)^n \end{bmatrix}$$

I guess it is equivalent to consider:

$$\begin{bmatrix} \sum_{i=1}^m 1 \\ \sum_{i=1}^mb_i \\ ... \\ \sum_{i=1}^m(b_i)^n \end{bmatrix}$$ $$\begin{bmatrix} 1 & 1 & ...& 1 \\ b_1 & b_2 & ... & b_m\\ ... & ... & ... & ... \\ (b_1)^n & (b_2)^n &... & (b_m)^n \end{bmatrix}$$

Now, let me explain why I think that we need much less vectors from the right side to represent the sum on the left. Notice that $$b_i < 1$$ and $$(b_i)^n$$ goes to $$0$$ very fast.

Then, after some $$k$$, $$(b_i)^k < \delta$$, and we could say that there are effectively $$k$$ linearly independent vectors in $$g(b_ix)$$:

$$\begin{bmatrix} 1 & 1 & ...& 1 \\ b_1 & b_2 & ... & b_m\\ ... & ... & ... & ... \\ (b_1)^k & (b_2)^k &... & (b_m)^k\\ 0 & 0 & ...& 0 \\ ... & ... & ... & ... \\ 0 & 0 &... & 0 \end{bmatrix}$$

Then we only need $$k$$ of $$g(b_ix)$$ to span $$\begin{bmatrix} a_0\sum_{i=1}^m 1 \\ a_1\sum_{i=1}^mb_i \\ ... \\ a_n\sum_{i=1}^m(b_i)^n \end{bmatrix}$$

How can I use this logic to prove that we can choose such $$g(b_ix)$$, so that: $$|f(x) - \sum_{i=1}^kc_ig(b_{j_i}x)| < \epsilon$$ for all $$x \in A$$

I don't know exactly what $$k$$ is, but I guess it should be something like:

$$mb^k < \epsilon, k > \frac{\log m - \log \epsilon}{ \log b}$$

I am not sure that my conjecture is true, so I will be very grateful if you show mistakes in my reasoning

The uniform norm makes approximability even (much) worse than in the vector projection case. Indeed, let $$g_0:\Bbb R\to\Bbb R$$ be a function such that $$g(x)=4x-2$$, if $$1/2\le x\le 3/4$$, $$g(x)= 4-4x$$, if $$3/4\le x\le 1$$, and $$g(x)=0$$, otherwise. Let $$A=[0,1]$$, $$g(x)=g_0(2^mx)$$ for each $$x\in A$$, and $$b_i=2^{-i}$$ for each $$1\le i\le m$$. Recall that a support $$\operatorname{supp} h$$ of a function $$h$$ is the set of $$x$$ such that $$h(x)\ne 0$$. The functions $$g(b_ix)$$ have mutually disjoint supports $$(2^{i-m-1},2^{i-m})$$, so if $$b_l$$ is missed in $$b_{j_i}$$ then for $$x=2^{m-l}\tfrac 34$$ we have $$f(x)=1$$, whereas $$\sum_{i=1}^kc_ig(b_{j_i}x)=0$$.
• Alex, I am sorry to disturb you again. May I ask your opinion, if I change uniform norm to $L^2$ norm will it make things any better? – Markoff Chainz Jun 8 at 18:11
• @MarkoffChainz I expect, no, with a similar counterexample. Assume thta we have a lot of distinct $b_i$ which are sufficiently close to a constant $b$ and $g(x)$ is a continuous function so similar to a characteristic function of a one-point set $\{1\}$ that supports of $g(b_i)$ are disjoint. Then if at least one $b_l$ is missed in $b_{j_i}$, we should have $$\|f(x)-\sum c_ig(b_{j_i}x) \|_2\ge \| g(b_lx)\|_2\simeq b\|g(x)\|_2.$$ – Alex Ravsky Jun 8 at 19:18
• @MarkoffChainz Corrigendum. I guess in the last formula should be $b^{-1}\|g(x)\|_2$ instead of $b\|g(x)\|_2$. – Alex Ravsky Jun 9 at 4:39