transform - 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?

Answer

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