1
vote
0answers
28 views

Formal inverse of a matrix ressembling Fourier's matrix

What is the formal inverse of a square $N\times N$ matrix $A$ with entries $A_{ij}=a^{(i-1)(j-1)}$? When $a$ is the $N$th root of unity (i.e. $a=\exp(2 \pi i/N)$), then $A$ is the Fourier matrix and ...
1
vote
0answers
19 views

Vector*Matrix multiplication through Fast Transforms

I have recently read a paper in which the authors indicated they used a Fast Cosine Transform to implement a Vector*Matrix multiplication. The idea is to decrease complexity when implementing such ...
0
votes
1answer
57 views

Multiply a circulant matrix by a vector with FFT.

I am asked to write a Matlab program to find the coefficients of the resulting polynomial which is the product of two other polynomials. However, I need someone to clarify the underlying concepts for ...
0
votes
2answers
35 views

discrete fourier transform proof (show equals n*I)

Let $w=e^{(-2\pi i/n)}$. Let $W$ be an $n \times n$ matrix defined by $$ W = \begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & w & w^2 & w^3 & \cdots & ...
0
votes
0answers
24 views

Significance of Mutual Coherence

I am reading about compressive sensing and I am not able to understand the physical significance of mutual coherence. For tow matrices $\Phi$ and $\Psi$, mutual coherence is defined as $\mu(\Phi, ...
0
votes
0answers
18 views

Polar form of Bi-Quatenrion

I have a complex Quaternion(Bi-quaternion) and i want to convert that to Polar form (Euler). Let say we have Fourier transform of a ( bi-quaternion ) like, then how can we get a polar form ...
1
vote
0answers
21 views

Is it possible to calculate a single frequency bin in $O(\log N)$ time (considering the $N\log N$ performance of FFT algorithms)?

Fast Fourier transform (FFT) algorithms are able to calculate the discrete Fourier transform (DFT) in only $O(N\log N)$ asymptotical time. Since there is roughly $N\log N$ operations for computing $N$ ...
2
votes
2answers
68 views

about Fourier transformation on zero-padded vector

I have a vector $x$ of n elements. I did a fft on it and return another vector of n elements also (i.e.$X = \text{fft}(x)$). Now I am trying to pad the $x$ vector by n zeros so to get $y$ $$ y = [x ...
1
vote
1answer
102 views

FFT of a matrix and its square.

I am doing something computationally intensive that requires that I compute the fast fourier transform of a matrix, let's say $A$, and also compute the FFT of its square, $A^2$. I am wondering if ...
3
votes
0answers
100 views

Does the Fourier matrix $F_n$ represent a (tensor) multiplicative function?

At "Complex Hadamard Matrices", I found that, two Kronecker (tensor) products of Fourier matrices $k_1$ and $k_2$ are equivalent, if and only if $k_2$ can be obtained from $k_1$ by a combination of an ...
0
votes
1answer
106 views

Decreasing the computational speed of Gaussian elimination of a complex linear system in a special case.

The solution of the complex linear system $Ax = b$ of $n$ equations can be computed using Gaussian elimination with $O(n^3)$ complex multiplications. However, how can we show that if ...
1
vote
0answers
84 views

Discrete fractional fourier transform

I have written a code for producing matrix of fractional fourier transform with the help of eigen vectors of fourier transfom matrix. Does anyone know the elements of this matrix ( for example a 4 by ...
1
vote
0answers
117 views

Matrix of Discrete fourier transform $F^4$ is identity

I already showed that Discrete fourier transform matrix is unitarian matrix. Now I would like to show that $F^4$ is identity. On wikipedia is written: "This can be seen from the inverse properties ...
2
votes
0answers
103 views

2-D DFT of a matrix PxP and 1-D DFT of a vector of size P^2?

What is the difference between the following two things: make a 2-D Discrete Fourier Transform of a certain matrix A[p,p], first reshape this matrix into a 1-D vector a[p^2,1], and compute the 1-D ...
1
vote
1answer
180 views

Finding the eigenvalues of the sum of circulant and diagonal matrices - What am I doing wrong?

Saw this question about the eigenvalues of the sum of circulant and diagonal matrices on MO and, since I recall my prof mentioned circulant matrices and Robert Gray's book, I thought I'd give it a ...
1
vote
2answers
259 views

Understanding Matrix Formula with Scant Knowledge of Linear Algebra

$n$ is a power of $2$. $M =\pmatrix{ 1& x_0 & x_0^2 & \dots &x_0^{n-1}\\\ 1& x_1 & x_1^2 & \dots &x_1^{n-1}\\&& \vdots\\1& x_{n-1} & x_{n-1}^{2} ...
4
votes
0answers
363 views

Fourier matrix - multiplicity of eigenvalues?

This question is Miscellaneous Exercise M.10 in Chapter 8 (Bilinear Forms) of Artin's Algebra. (The sentences in italics are due to me.) The row and column indices in the $n \times n$ Fourier ...
0
votes
1answer
464 views

Discrete Fourier Transform Matrix (DFT)

When does it occur that the eigenvalues of a Discrete Fourier Transform matrix are distinct?