Background (Mathematics)
If we have a matrix $D$ representing the Discrete Fourier Transform (DFT).
$$Dx = d$$ $$x = D^{-1}d$$
Now this is the standard straight-forward DFT. The matrix $D$ is dense.
The FFT in matrix language can be thought of as a factorization of this $D$ matrix.
$$D=F_1F_2\cdots F_nP$$ Where $P$ is a permutation matrix and the $F_k$ are sparse factor matrices with a small prime number of non-zero elements for each row, usually 2.
Background (Computer Graphics)
Imagine that we want to approximate a semi-transparent function coupled with a function like something which in the sense of computer graphics corresponds to an "alpha" value.
$\alpha \in [0,1]$ where $1$ means there is no see-through and $0$ means complete transparency.
Own approach
What we want to approximate is the function values of whatever is associated with this alpha map. For this purpose we can define a weighting function $\alpha \to w(\alpha) \in [0,1]$ where $w(0)=0$ and $w(1)=1$. In other words in areas where $\alpha$ tells us that the function needs to be well represented, the weight is high, and in areas where it is supposed to be completely transparent, the weight is close to $0$.
If we follow this approach we can create a diagonal $W$ matrix containing these values $w_{kk} = w(\alpha)$ for the corresponding positions where $d_k$ codes the function value.
$$WDx = Wd$$
Now we can set up the normal equations
$$D^TWDx = D^TWd$$ $$x = (D^TWD)^{-1} (D^TW)d$$
Would this be a viable alternative?
How would our knowledge about the above factorization of $D$ help us to speed up the solution of this problem in general?
Which strategies to solve the linear least squares problem would be most well suited to take advantage of it?