6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Just to be clear: You only want the maximum value and not the position? $\endgroup$
    – Jazzmaniac
    Commented Oct 21, 2016 at 9:39
  • 3
    $\begingroup$ More precisely, I want max(abs(x[n])) $\endgroup$
    – Kenneide
    Commented Oct 21, 2016 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$ Commented Mar 29, 2017 at 10:49

3 Answers 3

5
$\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$
3
$\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$
2
$\begingroup$

In addition to @MattL 's answer, I would like to provide an informal lower bound for the maximum, which may qualify between a rule of thumb and a complete nonsense, depending on the statistics of the signal.

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

The average value is: $$ \bar x = \frac {\sum_{n=0}^{N} {x[n]}} {N} = \frac{X[0]}N , \tag{2}$$ where $X[k]$ is the DFT of x[n]: $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} nk} \tag{3}$$

Standard deviation can be estimated as follows : $$\sigma_x^2 = \text{Var}(x) = E\{x^2\} - (E\{x\})^2 \tag{4}$$ replace $E\{x^2\}$ and $E\{x\}$ with their estimates: $$ E\{x^2\} = \frac{1}{N} \sum{x^2[n]} \tag{5}$$ and $$E\{x\} = \bar{x} . \tag{6}$$

Finaly, invoke Parseval's theorem to replace Eq.5 with : $$ \frac{1}{N} \sum_{n=0}^{N-1} x^2[n] = \frac {1}{N^2} \sum_{k=0}^{N-1} |X[k]|^2 . \tag{7}$$

Standard deviation is the square-root of the variance, we have the following expression as a lower bound for the maximum value of a (typical!) signal $x[n]$:

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

$\endgroup$
2
  • 3
    $\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
    Commented Oct 21, 2016 at 1:43
  • 1
    $\begingroup$ yes you are right, typical must be used with caution... $\endgroup$
    – Fat32
    Commented Oct 21, 2016 at 8:46

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.