Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the diagonalization of the discrete Fourier transform
136
0
0.0
(
0
)
Added by
Shamgar Gurevich
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Shamgar Gurevich
Ask ChatGPT about the research
No Arabic abstract
The discrete Fourier transform (DFT) is an important operator which acts on the Hilbert space of complex valued functions on the ring Z/NZ. In the case where N=p is an odd prime number, we exhibit a canonical basis of eigenvectors for the DFT. The transition matrix from the standard basis to the canonical basis defines a novel transform which we call the discrete oscillator transform (DOT for short). Finally, we describe a fast algorithm for computing the discrete oscillator transform in certain cases.
rate research
Read More
We consider the problem of secure distributed matrix computation (SDMC), where a textit{user} can query a function of data matrices generated at distributed textit{source} nodes. We assume the availability of $N$ honest but curious computation servers, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the textit{upload cost}, while guaranteeing that no $T$ colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, as well as to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any $T$ colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure.
In this work, we present two parallel algorithms for the large-scale discrete Fourier transform (DFT) on Tensor Processing Unit (TPU) clusters. The two parallel algorithms are associated with two formulations of DFT: one is based on the Kronecker product, to be specific, dense matrix multiplications between the input data and the Vandermonde matrix, denoted as KDFT in this work; the other is based on the famous Cooley-Tukey algorithm and phase adjustment, denoted as FFT in this work. Both KDFT and FFT formulations take full advantage of TPUs strength in matrix multiplications. The KDFT formulation allows direct use of nonuniform inputs without additional step. In the two parallel algorithms, the same strategy of data decomposition is applied to the input data. Through the data decomposition, the dense matrix multiplications in KDFT and FFT are kept local within TPU cores, which can be performed completely in parallel. The communication among TPU cores is achieved through the one-shuffle scheme in both parallel algorithms, with which sending and receiving data takes place simultaneously between two neighboring cores and along the same direction on the interconnect network. The one-shuffle scheme is designed for the interconnect topology of TPU clusters, minimizing the time required by the communication among TPU cores. Both KDFT and FFT are implemented in TensorFlow. The three-dimensional complex DFT is performed on an example of dimension $8192 times 8192 times 8192$ with a full TPU Pod: the run time of KDFT is 12.66 seconds and that of FFT is 8.3 seconds. Scaling analysis is provided to demonstrate the high parallel efficiency of the two DFT implementations on TPUs.
In this paper, we redefine the Graph Fourier Transform (GFT) under the DSP$_mathrm{G}$ framework. We consider the Jordan eigenvectors of the directed Laplacian as graph harmonics and the corresponding eigenvalues as the graph frequencies. For this purpose, we propose a shift operator based on the directed Laplacian of a graph. Based on our shift operator, we then define total variation of graph signals, which is used in frequency ordering. We achieve natural frequency ordering and interpretation via the proposed definition of GFT. Moreover, we show that our proposed shift operator makes the LSI filters under DSP$_mathrm{G}$ to become polynomial in the directed Laplacian.
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in $R^n$, that generalizes the $n$-th fold DFT of the integer lattice $Z^n$ to arbitrary lattices. This definition is not applicable for every lattice, but can be defined on lattices known as Systematic Normal Form (SysNF) introduced in cite{ES16}. Systematic Normal Form lattices are sets of integer vectors that satisfy a single homogeneous modular equation, which itself satisfies a certain number-theoretic property. Such lattices form a dense set in the space of $n$-dimensional lattices, and can be used to approximate efficiently any lattice. This implies that for every lattice $L$ a DFT can be computed efficiently on a lattice near $L$. Our proof of the statement above uses arguments from quantum computing, and as an application of our definition we show a quantum algorithm for sampling from discrete distributions on lattices, that extends our ability to sample efficiently from the discrete Gaussian distribution cite{GPV08} to any distribution that is sufficiently smooth. We conjecture that studying the eigenvectors of the newly-defined lattice DFT may provide new insights into the structure of lattices, especially regarding hard computational problems, like the shortest vector problem.
Estimation of the Discrete-Time Fourier Transform (DTFT) at points of a finite domain arises in many imaging applications. A new approach to this task, the Golden Angle Linogram Fourier Domain (GALFD), is presented, together with a computationally fast and accurate tool, named Golden Angle Linogram Evaluation (GALE), for approximating the DTFT at points of a GALFD. A GALFD resembles a Linogram Fourier Domain (LFD), which is efficient and accurate. A limitation of linograms is that embedding an LFD into a larger one requires many extra points, at least doubling the domains cardinality. The GALFD, on the other hand, allows for incremental inclusion of relatively few data points. Approximation error bounds and floating point operations counts are presented to show that GALE computes accurately and efficiently the DTFT at the points of a GALFD. The ability to extend the data collection in small increments is beneficial in applications such as Magnetic Resonance Imaging. Experiments for simulated and for real-world data are presented to substantiate the theoretical claims. The mathematical analysis, algorithms, and software developed in the paper are equally suitable to other angular distributions of rays and therefore we bring the benefits of linograms to arbitrary radial patterns.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
