3
$\begingroup$

Is it possible to calculate the maximum value of a time-domain signal from frequency-domain representation without performing an inverse transform?

$\endgroup$
  • $\begingroup$ Just to be clear: You only want the maximum value and not the position? $\endgroup$ – Jazzmaniac Oct 21 '16 at 9:39
  • 2
    $\begingroup$ More precisely, I want max(abs(x[n])) $\endgroup$ – Kenneide Oct 21 '16 at 10:04
  • 1
    $\begingroup$ Hi: Just a gentle reminder that you've got three nice answers now, but haven't accepted one this far. Might be a good time to do that! $\endgroup$ – Marcus Müller Mar 29 '17 at 10:49
3
$\begingroup$

Suppose that Alice has a vector $\mathrm x \in \mathbb R^n$. She computes the DFT of $\mathrm x$

$$\mathrm y := \mathrm F \mathrm x \in \mathbb C^n$$

where $\mathrm F \in \mathbb C^{n \times n}$ is a Fourier matrix. Alice then tells Bob what $\mathrm y$ is. Since the inverse of the Fourier matrix is $\mathrm F^{-1} = \frac 1n \, \mathrm F^*$, Bob can recover $\mathrm x$ via

$$\mathrm x = \frac 1n \, \mathrm F^* \mathrm y$$

and then compute $\| \mathrm x \|_{\infty}$ to find the maximum absolute value of the entries of $\mathrm x$. What if computing matrix inverses and Hermitian transposes is not allowed? Bob can then write $\mathrm F$ and $\mathrm y$ as follows

$$\mathrm F = \mathrm F_{\text{re}} + i \,\mathrm F_{\text{im}} \qquad \qquad \qquad \mathrm y = \mathrm y_{\text{re}} + i \,\mathrm y_{\text{im}}$$

and, since $\mathrm x \in \mathbb R^n$, the equation $\mathrm F \mathrm x = \mathrm y$ yields two equations over the reals, namely, $\mathrm F_{\text{re}} \, \mathrm x = \mathrm y_{\text{re}}$ and $\mathrm F_{\text{im}} \, \mathrm x = \mathrm y_{\text{im}}$. Bob can then solve the following linear program in $t \in \mathbb R$ and $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & - t 1_n\leq \mathrm x \leq t 1_n\\ & \begin{bmatrix} \mathrm F_{\text{re}}\\ \mathrm F_{\text{im}}\end{bmatrix} \mathrm x = \begin{bmatrix} \mathrm y_{\text{re}}\\ \mathrm y_{\text{im}}\end{bmatrix}\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & \begin{bmatrix} 1\\ 0_n\end{bmatrix}^{\top} \begin{bmatrix} t\\ \mathrm x \end{bmatrix}\\ \text{subject to} & \begin{bmatrix} -1_n & \mathrm I_n\\ -1_n & -\mathrm I_n\end{bmatrix} \begin{bmatrix} t\\ \mathrm x \end{bmatrix} \leq \begin{bmatrix} 0_n\\ 0_n\end{bmatrix}\\ & \begin{bmatrix} 0_n & \mathrm F_{\text{re}}\\ 0_n & \mathrm F_{\text{im}}\end{bmatrix} \begin{bmatrix} t\\ \mathrm x \end{bmatrix} = \begin{bmatrix} \mathrm y_{\text{re}}\\ \mathrm y_{\text{im}}\end{bmatrix}\end{array}$$

and not only recover $\mathrm x$ but also obtain $t = \| \mathrm x \|_{\infty}$. However, is solving a linear program cheaper than computing a Hermitian transpose?


MATLAB code

The following MATLAB script

n = 8;

% build n x n Fourier matrix
F = dftmtx(n);

% -----
% Alice
% -----

% build vector x
x = randn(n,1);

% compute DFT of x
y = F * x;

% ---
% Bob
% ---

% solve linear program
c = eye(n+1,1);
A_in = [-ones(n,1), eye(n);
        -ones(n,1),-eye(n)];
b_in = zeros(2*n,1);
A_eq = [zeros(n,1), real(F);
        zeros(n,1), imag(F)];
b_eq = [real(y); imag(y)];
solution = linprog(c, A_in, b_in, A_eq, b_eq);

% extract t and x
t = solution(1);
x_rec = solution(2:n+1);

% check results
disp('t = '); disp(t);
disp('Infinity norm of x = '); disp(norm(x,inf));
disp('Reconstruction error = '); disp(x_rec - x);

produces the output

Optimization terminated.
t = 
2.2023

Infinity norm of x = 
2.2023

Reconstruction error = 
1.0e-013 *

0.0910
0.0711
0.0167
-0.1077
0.1049
0.0322
0.1130
0.2776

The original vector is

>> x

x =

-1.1878
-2.2023
0.9863
-0.5186
0.3274
0.2341
0.0215
-1.0039
$\endgroup$
2
$\begingroup$

It's generally not possible to compute the exact maximum value, but you can compute a bound on the maximum value. Assuming your data are discrete-time, and you're using the discrete Fourier transform (DFT), you have the following relation between time domain and frequency domain:

$$x[n]=\frac{1}{N}\sum_{n=0}^{N-1}X[k]e^{j2\pi kn/N}\tag{1}$$

where $N$ is the DFT length. From $(1)$ we can derive the following bound:

$$|x[n]|=\frac{1}{N}\left|\sum_{n=0}^{N-1}X[k]e^{j2\pi kn/N}\right|\le\frac{1}{N}\sum_{n=0}^{N-1}\left|X[k]\right|\left| e^{j2\pi kn/N}\right|=\frac{1}{N}\sum_{n=0}^{N-1}\left|X[k]\right|\tag{2}$$

For other types of (Fourier) transforms (DTFT, CTFT), similar bounds can be derived in the same way.

$\endgroup$
0
$\begingroup$

In addition to @MattL 's answer, which provides a method to compute a strict upper bound for the maximum of a signal $x[n]$ from its DFT $X[k]$, I would like to provide an informal (without any proofs) lower bound for the maximum, which can also be benefical at times.

Now my loose claim without any proof is that for a typical signal x[n], its maximum sample is expected to be larger (or not less) than the sum of its average value $\bar x$ and its standard deviation $\sigma_x$ : $$x_{max} > \sigma_x + \bar x $$

The average value of a signal is estimated as: $$ \bar x = \frac {\sum_{n=0}^{N} {x[n]}} {N}$$ And this is nothing but $ \frac{X[0]}N$, where $X[k]$ is the DFT of x[n] given by: $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} nk} $$

Now, to find an estimate of standard deviation, $\sigma_x$, we can use the following trick: $$\sigma_x^2 = \text{Var}(x) = E\{x^2\} - (E\{x\})^2$$ and replace $E\{x^2\}$ and $E\{x\}$ with the following estimates: $$ E\{x^2\} = \frac{1}{N} \sum{x[n]^2} $$ and $E\{x\}$ is already estimated as $\bar x$.

Finaly we can invoke Parseval's theorem to compute the squarred sum which equals the total energy of the signal: $$\sum_{n=0}^{N-1} x[n]^2 = \frac {1}{N} \sum_{k=0}^{N-1} |X[k]|^2 $$

Since standard deviation is the square of the variance , we can have the following expression as a lower bound for the maximum value of a signal $x[n]$

$$ x_{max} > \frac { \sqrt{ \sum_{k=0}^{N-1} |X[k]|^2 - X[0]^2} } {N} + \frac {X[0]}{N} $$

Note that if you're bold enough you can further claim that the typical maximum will be less than average plus 4 times the standard deviation with 0.999 probability (for a gaussian distribution) i.e. $$x_{max} < \bar x + 3 \sigma_x$$ which can also be computed simply from above, hence a total bound for a typical maximum sample can be defined as: $$ \bar x + \sigma_x < x_{max} < \bar x + 3\sigma_x $$

$\endgroup$
  • 2
    $\begingroup$ It seems you are using Chebyshev's inequality in your answer which makes sense in a probabilistic framework. But I suggest a tighter definition for the term typical signal to avoid confusion for not-so-expert readers. For instance, with n=-5:5and x=-(n+2).^2 it seems $x_{max}>\sigma_x+\bar{x}$ cannot be used. $\endgroup$ – msm Oct 21 '16 at 1:43
  • 1
    $\begingroup$ yes you are right, typical must be used with caution... $\endgroup$ – Fat32 Oct 21 '16 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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