Continuing the discussion from Convolution kernel in Bluestein's algorithm it has a very specific signature of the kernel
[conj(W), zeros(1, L-2*N+1), conj( W(N:-1:2) )];
for the fast-convolution.
There W is the chirp specific to Bluestein's algorithm
If not W would such a signature applicable for any general data?
I personally have one problem where the output length after the convolution must be same as the input vector length.
Perhaps I am over-complicating the things here. If I visualize the convolution it boils to very simple.
S = [1 2 3];
T = [2 0 0];
G = ifft( fft(S).*fft(T) )
and if I extand to $\ell=4$ samples then
L = 4
S = [1 2 3 1 2 3 1 2 3 1 2 3];
T = [2 0 0 2 0 0 2 0 0 2 0 0];
G = ifft( fft(S).*fft(T) ) / L
I may think this is the solution.
To answer the question: No it will not be the same in general form.
What is general form is for the second half of the vector to represent the time reversed samples for the function used so that the result is identical to linear convolution with no time offset or delay (so a non-causal operation that we do with post processing).
Such for any general time domain waveform with $N$ samples given by $[x[0], x[1], \ldots x[N-1]]$ where x[0] represents the sample at time in samples at $n=0$, for a “zero-phase” linear convolution we would perform the convolution with the $2N-1$ samples given by $[x[-N+1], x[-N+2], \ldots x[-1], x[0], x[1], \ldots x[N-1]$.
Notice how for the case of $W[n]= e^{2\pi n^2/N}$ specifically, the first half of the above is simply $W$ in reverse order, but generally this is not the case (when used in a transform where the resulting transform is real, we would use the time reversed complex conjugate, and when the result complex it can be completely independent and should be computed directly for the negative indexes).
Next an $N$ length output was used and for the Bluestein Algorithm specifically it is the last $N$ samples of the linear convolution, associated with $n=0$.
When this same convolution is done using FFT’s for the fast convolution technique the form given by the OP results and it will be the first $N$ samples of the result that would match the last $N$ samples of the linear convolution of computed directly. This is how the output samples match the input samples (a subset of the samples is selected) and how to set up the array in general form.
To answer the question as to how to do the convolution in general form with $N$ samples out for $N$ samples in, we must first clarify if a circular or linear convolution is desired. If circular convolution is desired, then the fast convolution will return $N$ samples for $N$ samples in (of each waveform). If a linear convolution is desired, this is done with zero padding as detailed in the referenced posts below, and here we note that the result of linear convolution of two waveforms will be $M+N-1$ samples long when one of the waveforms has $M$ samples and the other has $N$ samples. Therefore we need to specify which $N$ samples of the output we wish to have.
Further details relating to Bluestein's Algorithm
With that said we can see how this applies specifically to what motivated this question, further detailed here and here- notably the derivation of using FFT's with efficient power of 2 lengths to compute prime-length DFT's via Bluestein's Algorithm. The second link details specifically step by step how the Algorithm is computed, but note for here that a linear convolution of an $N$ sample sequence $y[n]$ with a chirp signal given as $h^{-1}[n] = W_N^{-n^2/2}[n]$, notably defined for $n$ with negative index values from -$N+1$ to $N-1$. The inverse is not important to this explanation, so I will further simplify by using $g[n]= h^{-1}[n]$. Further, for this chirp signal specifically (and not universally to any signal), $g[-n] = g[n]$. Given this, the graphic below represents the linear convolution specified, shown with arbitrary waveforms but notably to depict that $g[n]$ is defined for $n=-N+1\ldots N-1$ and zero elsewhere, and has symmetry about $n=0$ but $y[n]$ is defined for $n=0 \ldots N-1$:
The linear convolution result of the above would have a first non-zero value at $n=-N+1$ and would continue for a total $3N-2$ samples. However, it is only the $N$ samples starting at $n=0$ that are needed for Bluestein's Algorithm (see the referenced post detailing why). Thus if we were to do the linear convolution directly, it would be formed as follows using $g[n]$ as the $N$ samples from $n=0 \ldots N-1$ and equal to conj(W) used by the OP:
result = xcorr(y, [g(N:-1:2), g]);
The first sample of this result corresponds to $n=N+1$, we would would extract the $N$ sample sequence starting with the Nth sample:
result(N:2*N-1)
The above operations are in the derivation of Bluestein's Algorithm and notably showing how a DFT of a sequence can be computed by multiplying with a chirp, convolving that product with the inverse of the chirp (including the negative index values as explained here) and then multiplying the proper $N$ samples of that result with the chirp. Where the question and concern with "zero padding" comes up is in using the FFT for "fast convolution" and for that I reference the first post specifically, where in my answer, I detail how padding in the center of the sequence when doing a DFT or inverse DFT is necessary to achieve the same linear convolution result. Specifically the following would give us identical results to the $N$ samples needed as done above, out to any length FFT (and for this reason specifically, the algorithm is attractive as we can use power of 2 length FFT's which are very efficient).
result = ifft(fft([g, zeros(1, L-2*N+1), g(N:-1:2)]) * fft(y));
result(1:N)
comes in two major 'flavors':
impulse response: output of a (LTI) system in response to an input
len(out) > len(in) (for len(h) > 1), namely, len(out) == len(in) + len(h) - 1.x[i]" means kernel starts at x[i] (see further in answer)correlation, i.e. cross-correlation / template matching: measuring similarity of input with the convolution kernel
len(out) == len(in).x[i]" means kernel is centered at x[i]I will explain padding for #2, but everything can be translated to 1 from the bullet points.
The basic idea is, "left shall not draw from right". That is, the convolution kernel, $h$, when at one edge of $x$, is not present at the other edge. Suppose
$$ x = [1, 2, 3], h = [5, -1, 6] $$
"$h$ is at $x[n_0]$" means $h$ is centered there ("kernel at").
No padding, $h$ at $x[0]$:
[1, 2, 3]
[-1, 6, 5]
Here, $h$'s left, which is $5$, draws from $x$'s right, which is $3$. Similar story when $h$ is at $x[-1]$. (Note, $h$'s left "wraps" around to right because FFT convolution is circular)
Sufficient zero padding, $h$ at $x[0]$:
[0, 1, 2, 3, 0]
[5, -1, 6, 0, 0]
Here, $h$'s left, which is $5$, is at $0$, which doesn't touch $x[-1]$, which is $3$.
Visualized:
Blue = $x$, green = $h$, red = boundaries of $x$ (i.e. unpadded region of $x$). $h$ can be anything here, I picked boxcar for clarity. What matters is, when it's at $x[0]$, its left is zero at $x[-1]$, and when it's at $x[-1]$, and vice versa.
Input size == output size just means we only keep results of convolution where $h$ is at $x$, rather than at padded $x$. There's no restriction on $x$ or $h$ (though the quality of our results can surely vary, e.g. if $h$ is much longer than $x$).
This MATLAB guide demonstrates linear convolution, i.e. #1. It right-pads both the input and the kernel, meaning the kernel isn't centered, and we also unpad to len(out) > len(in). With a few tweaks as per bullets, we can convert this code to #2 - as in Bluestein's algorithm.
Finally, a caveat: any non-zero padding requires double the length of zero padding (because then "left" and "right" include the padded portions).
