4
$\begingroup$

I want to minimize the $L_1$ norm of a finite odd-term trigonometric polynomial:

$$\min_{a_k} \int_{0}^{1} |\sin(2\pi t)+\sum_{k \in \{3,5,7,...,2K-1\}}a_k\sin(2\pi kt)| \, \mathrm d t$$

Obviously, if the minimization was done in $L_2$, all $a_k$s would be zero since all the involved sinusoids are orthogonal on $[0,1]$. I have done Matlab experiments that show some reduction of the $L_1$ norm by carefully selecting the values for $a_3$ and $a_5$, but these values were found using a grid search.

Is there a way of computing the coeffs $a_3$ up to $a_{2K-1}$ analytically?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Not a full answer but too long for a comment.

We rewrite the problem as follows: Define $A:\mathbb{R}^n\to L^1(0,1)$ by $Aa(t) = \sum_k a_k\sin(2\pi kt)$. Then the problem is $$ \min_a \|f-Aa\|_1 $$ with $f(t) = \sin(2\pi t)$ and this is a convex minimization problem in finite dimensions. A necessary and sufficient condition for $a^*$ to be optimal is $$ 0\in A^*\operatorname{Sign}(f-Aa^*) $$ where $\operatorname{Sign}$ is the multivalued sign, i.e. $$ \operatorname{Sign}(f(x)) = \begin{cases}\{1\} & f(x)>0\\ [-1,1] & f(x)=0\\\{-1\} & f(x)<0\end{cases} . $$ The adjoint operator $A^*:L^\infty(0,1) \to \mathbb{R}^n$ is $$ (A^*g)_k = \int_0^1 g(t)\sin(2\pi kt)dt. $$ In other words: $a^*$ is optimal if there is a $g\in L^\infty(0,1)$ such that

i) $g(t) \in \operatorname{Sign}(f(t)-Aa^*(t))$ almost everwhere, and

ii) $\int_0^1 g(t) \sin(2\pi kt)dt = 0$ for all $k$.

I did not try to solve this for your actual $f$, though.

In fact, approximation in $L^1$ is a well studied subject and if you search for "trigonometric approximation in L^1" you'll find the paper "Interpolation and L1-approximation by trigonometric polynomials and blending functions" which may be helpful.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer! Only problem is that you have shown the dual optimization problem (i) and ii)). That was my original problem, which I found hard to solve, believing the L1-norm minimization would be easier...:-) $\endgroup$ Jan 20, 2017 at 16:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.