6
$\begingroup$

Consider vector X =( X_1 ... X_N), consider the discrete Fourier transform $Y=F(X)$.

I am interested to minimize $|Y|_{\infty}$, by permutation of numbers X_i, how to do it ?

Here $|Y|_{\infty}$ is infinity norm of the vector Y i.e. just the maximum of absolute values of components of Y.


More close to life problem is a little more complicated: my numbers X_i are splited at several subsequences such that |X|=const in each subsequence. And I am allowed to make "block" permutations of these subsequences. The goal is the same as to minimize $|Y|_{\infty}$


Background: roughly speaking the OFDM based ( = most advanced) radio telecommunication systems (LTE, WiMax, new WiFi) make the Fourier transform before transmitting data symbols to the space. Average power is fixed, but people care also about the maximal instant power, which they do not want to be big. Instant power is just the maximal component of the vector.

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't see how you can do anything non-trivial without additional restrictions on $X$. The trivial estimate is $|Y|{\infty} \leq |X|_{1}$ (assuming there is no normalizing factor in your definition of F, which, in any event, doesn't change the argument). However, taking $X=(1,1,\ldots 1)$ one sees that this is in fact an equality (for any reordering of the $X_i$'s).

$\endgroup$
4
  • $\begingroup$ May be I did not formulate the question correctly. I mean for GIVEN sequence of (X_1 ... X_N) how to find permutation that minimize ... ? Of course, if X_i=X_j then nothing can be done. $\endgroup$ Oct 15, 2012 at 11:38
  • $\begingroup$ Also, if X_i are positive real than |Y|_inf = |X|_1 , and permutation will not have any effect. $\endgroup$ Oct 15, 2012 at 11:40
  • $\begingroup$ That was exactly my point. If there is a choice of X such that no reordering improves over the trivial estimate, what do you expect an answer to look like? $\endgroup$
    – Mark Lewko
    Oct 15, 2012 at 23:38
  • $\begingroup$ What about other X such that reordering will work? How to choose optimal or suboptimal reordering? $\endgroup$ Oct 29, 2012 at 16:28

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.