# Time domain maximum from frequency domain data?

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

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

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


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.

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}$$

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