A non-transitory computer-readable storage medium having stored thereon a program that, when executed by a processor, causes the processor to execute a fast multidimensional partial Fourier transform method for real-time digital signal processing in autonomous vehicle being performed by a fast multidimensional partial Fourier transform apparatus including an input interface, a communication interface, and the processor, the method comprising:
- receiving, by the input interface, multidimensional data and receiving a fast multidimensional partial Fourier transform request for the multidimensional data;
- converting, by the processor, the multidimensional data into frequency domain by utilizing an energy compression property of the multidimensional data in the frequency domain, thereby outputting multidimensional Fourier coefficient data according to fast multidimensional partial Fourier transform;
- and
- transmitting, by the communication interface, the multidimensional Fourier coefficient data for the multidimensional data,
- wherein the outputting the multidimensional Fourier coefficient data according to the fast multidimensional partial Fourier transform comprises:
- setting a plurality of hyperparameter data used in a partial Fourier transform based on constraints on tolerance data and degree data of a polynomial for polynomial approximation, wherein the setting the plurality of hyperparameter data comprises automatically selecting the plurality of hyperparameter data using a convex optimization-based algorithm to minimize computational cost;
- and
- approximating and computing multidimensional Fourier coefficient data of the partial Fourier transform for the multidimensional data based on the plurality of hyperparameter data to output approximated multidimensional Fourier coefficient data for controlling navigation of the autonomous vehicle, wherein the multidimensional data represents inputs from the autonomous vehicle,
- wherein the setting the plurality of hyperparameter data comprises:
- setting multidimensional degree data using unconstrained convex optimization based on the constraints;
- setting multidimensional divisor data based on a size of an array adapted to store the multidimensional Fourier coefficient data, and the multidimensional degree data;
- setting multidimensional quotient data based on the size of the array adapted to store the multidimensional Fourier coefficient data, and the multidimensional divisor data;
- setting multidimensional range tensor data based on the size of the array adapted to store the multidimensional Fourier coefficient data, the multidimensional degree data, and the multidimensional quotient data;
- and
- setting optimal parenthesization data for an operation representing the multidimensional Fourier coefficient data using the multidimensional range tensor data, and
- wherein the approximating and computing the multidimensional Fourier coefficient data comprises:
- generating a first tensor data by performing block decomposition on an array adapted to store the multidimensional Fourier coefficient data based on the multidimensional divisor data and the multidimensional quotient data;
- converting the first tensor data and the multidimensional range tensor data into a second tensor data by performing sequential tensor data product operations on the first tensor data and the multidimensional range tensor data based on the optimal parenthesization data;
- converting the second tensor data into a third tensor data by permuting the second tensor data based on the multidimensional degree data;
- converting the third tensor data into a fourth tensor data by applying a fast Fourier transform to the third tensor data;
- and
- performing a dot product operation on the fourth tensor data, to which the fast Fourier transform has been applied, based on the multidimensional divisor data and a multidimensional output area, and outputting an array in which the approximated multidimensional Fourier coefficient data has been stored.