The goal of the project is to develop efficient algorithms and implementations of sparse Fourier Transform, and apply them to specific application domains, such as networked system for delivering smart services.
Major Activities:
Chronos: We have developed a system, called Chronos, which enables a single WiFi access point to localize clients to within tens of centimeters. The key tool is a novel algorithm that can compute sub-nanosecond time-of-flight of wireless signals using commodity WiFi cards. By multiplying the time-of- flight with the speed of light, an access point computes the distance between each of its antennas and the client, enabling localization. The key challenge faced by the system is that wireless signals typically travel along multiple paths, so the time-of-flight is not determined by a single parameter. To recover the multipath profile of a signal, we need to efficiently solve the inverse Non-uniform Fourier Transform (NFT). The later is an under-determined system of equations, where only the responses of some frequencies are available. To find the times of flight, Chronos adds a constraint that favors solutions that are sparse, i.e., have few dominant paths. This makes it possible to identify all significant multipath arrival times, and solve the problem.
Our implementation of Chronos on commodity WiFi cards demonstrates that its accuracy is comparable to state-of-the-art localization systems which use four or five access points. Specifically, Chronos computes the time-of-flight with a median error of 0.47 ns in line-of-sight and 0.69 ns in non-line-of-sight settings. This corresponds to a median distance error of 14.1 cm and 20.7 cm respectively
Broader Impact: Chronos' accuracy makes it possible to use it for multiple applications. In particular, we demonstrate that it can be used to track the number of occupants in different rooms of a home using a single access point - a key primitive for smart home; it can be used by small businesses with a single access point to restrict WiFI connectivity to customers within their facility; and it can benefit navigation systems of personal robots such as recreational drones.
Hadamard Transform: We investigated robust and efficient deterministic algorithms for the sparse Walsh-Hadamard transform (the Discrete Fourier Transform over the Boolean cube). All such algorithms developed so far had running times that were at least quadratic in the sparsity of the signal. This stands in contrast with randomized algorithms, whose running times are linear in the sparsity parameter.
In a paper published at SODA’16, we present an approximate algorithm that breaks the aforementioned “quadratic time barrier”. In particular, it computes the Walsh-Hadamard transform of an n-dimensional vector with sparsity parameter k in time k^(1+α) (log n)^O(1) for any constant α>0. The algorithm is robust, i.e., it works even for signals that are only approximately k-sparse (as measured by the L1 norm). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers, which enable us to deterministically “simulate” the random process used in earlier randomized algorithms.
Beam alignment: We designed an algorithm that performs a small number of amplitude-only measurements of a Fourier-sparse vector using "phase shifter" matrices. The algorithm uses only M=O(K log N) measurements for signals that are K-Fourier-sparse. We then used the algorithm to build a beam-alignment system for mmWave radios, and tested it empirically. Our system reduces the beam alignment delay by orders of magnitude. In particular,for highly directional mmWave devices operating under 802.11ad, the delay drops from over a second to 2.5 ms.
