I'm currently working on an interesting problem in function approximation thta just came to mind and am seeking insights or methodologies that might aid in approaching it. The problem is as follows:
Given a continuous function say, $f(x) = \sin(x)$, I want to find a polynomial $P(x)$ of degree $n$, where each coefficient of $P(x)$ is constrained to either $1$ or $-1$. The objective is to devise an algorithm that finds the polynomial $P$ minimizing the integral of the squared discrepancy between $f(x)$ and $P(x)$ across the interval $[-\pi,\pi]$, succinctly put as:
$$\min_{P \in \mathcal{P}} \int_{-\pi}^{\pi} (f(x) - P(x))^2 \, dx$$
Here, $\mathcal{P}$ represents the set of all polynomials of degree $n$ with coefficients from the set $\{1, -1\}$.
This scenario introduces a unique constraint on polynomial approximation due to the binary nature of the coefficients. I'm pondering how one might efficiently tackle this problem, especially as $n$ becomes large, given the expansive nature of the search space.
Could there be methodologies within numerical analysis, approximation theory, or combinatorial optimization that might be adapted or leveraged to unearth a solution? I'm particularly curious about any probabilistic algorithms, heuristic strategies, or other approaches that could effectively navigate the search space.
I greatly appreciate any suggestions, insights, or guidance the community can offer on this matter.
Thank you in advance for your assistance!
PS:We can anyhow do the problem by exhaustive a search in exponential time.My point is can we do it better somehow.
Let $P(x) = \sum_{k=0}^n t_k x^k$, where you want $t_k = \pm 1$. Expanding out $(f(x) - P(x))^2$ and integrating, your objective is a quadratic form $$ a + \sum_k b_k t_k + \sum_{j,k} c_{j,k} t_j t_k $$ for some real constants $a$, $b_k$, $c_{j,k}$. Write $t_k = 2 x_k-1$ and this is a Quadratic unconstrained binary optimization problem, a type of problem that is well studied, in particular because quantum annealing is one way of attacking it.