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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.