distributed; they follow a specific structure. For example, as mentioned earlier, in wireless communication, the occupied frequencies in the wireless spectrum are clustered. In computational photography, the occupied frequencies are more likely to be present in part of the Fourier spectrum. On the other hand, in an application like GPS, the occupied coefficient can be anywhere. Understanding the structure of sparsity in each application allows us to design a system that leverages it to achieve the best performance gains.
Level of Sparsity. A main difference between theory and practice is that the Sparse Fourier Transform algorithms operate in the discrete domain. In real and natural signals, however, the frequency coefficients do not necessarily lie on discrete grid points. Simply rounding off the locations of the coefficients to the nearest grid points can create bad artifacts which significantly reduce the sparsity of the signal and damage the quality of the results. This problem occurs in application like medical imaging and light-field photography. Hence, we have to design systems that can sparsify the signals and recover their original sparsity in the continuous domain in order to address the mismatch between the theoretical Sparse Fourier Transform framework and the scenarios in which it is applied.
Table 1.2 Theoretical Sparse Fourier Transform algorithms
a. The sampling complexity of algorithms SFT 1.0–4.1 is the same as their runtime complexity.
System Requirements. Different applications have different goals. For example, in medical imaging, the acquisition cost is high since it requires the patient to spend more time in the MRI machine while processing the captured data afterward is not a problem. Hence, the goal would be to minimize the number of input samples that need to be collected even if it requires additional processing time. On the other hand, in applications like GPS, collecting the samples is very cheap. However, processing them consumes a lot of power. Hence, the goal would be to minimize computational load even if all the input samples are used. Finally, in applications like spectrum acquisition and NMR spectroscopy, the goal would be to minimize both the runtime and the sampling. Hence, understanding the system is essential for adapting the Sparse Fourier Transform techniques to satisfy the requirements of each application.
System Architecture. In some applications, the applicability of the Sparse Fourier Transform to a system architecture might not even be apparent. For example, the Fourier transform of the GPS signal is not sparse and hence applying the Sparse Fourier Transform directly to GPS is not feasible. However, we observed that the GPS receiver correlates its signal with a special code transmitted by the satellite, and the output of the correlation is sparse because it spikes only when the code and the signal are aligned. Hence, we have to map this indirect form of sparsity to the Sparse Fourier Transform framework. We also need to ensure that the gains of the Sparse Fourier Transform are not bottlenecked by other components in the system. Thus, careful system design is essential for propagating these gains along the system pipeline and improving the overall system performance.
Signal to Noise Ratio. In practice, the gains of the Sparse Fourier Transform are constraint by the noise level in the system. It is essential to perform sampling and processing that would be sufficient to bring the signal above the noise floor of the system. For example, although the sparsity that appears in a GPS system is extremely high (≈0.025%), GPS signals are -30 dB to -20 dB below the noise floor which requires additional computation that upper bounds the performance gains. Thus, understanding the noise level and structure is essential in designing any system that uses the Sparse Fourier Transform.
The following subsections summarize the systems presented in this book and how they benefit from the Sparse Fourier Transform.
1.2.1 Spectrum Sensing and Decoding
The ever-increasing demand for wireless connectivity has led to a spectrum shortage which prompted the FCC to release multiple new bands for dynamic spectrum sharing. This is part of a bigger vision to dynamically share much of the currently under-utilized spectrum, creating GHz-wide spectrum superhighways that can be shared by different types of wireless services. However, a major technical obstacle precluding this vision is the need for receivers that can capture and sense GHz of spectrum in real-time in order to quickly identify unoccupied bands. Such receivers consume a lot of power because they need to sample the wireless signal at GigaSample/s.
To overcome this challenge, we leverage the fact that the wireless spectrum is sparsely utilized and use the Sparse Fourier Transform to build a receiver that can capture and recover GHz of spectrum in real-time, while sampling only at MegaSample/s. We use the aliasing filters and phase rotation techniques described in Section 1.1.3 to build the entire receiver using only cheap, low power hardware similar to what is used today by WiFi and LTE in every mobile phone. We implement our design using three software radios, each sampling at 50 MegaSample/s, and produce a device that captures 0.9 GHz, i.e., 6× larger digital bandwidth than the three software radios combined. The details of the system design, implementation, and evaluation can be found in Chapter 7.
1.2.2 GPS Receivers
GPS is one of the most widely used wireless systems. In order to calculate its position, a GPS receiver has to lock on the satellite signals by aligning the received signal with each satellite’s code. This process requires heavy computation, which consumes both time and power. As a result, running GPS on a phone can quickly drain the battery.
We introduced a new GPS receiver that minimizes the required computation to lock on the satellite’s signal hence reducing localization delay and power consumption. Specifically, we observed that GPS synchronization can be reduced into a sparse computation problem by leveraging the fact that only the correct alignment between the received GPS signal and the satellite code causes their correlation to spike. We built on this insight to develop a GPS receiver that exploits the Sparse Fourier Transform to quickly lock on the satellite signal and identify its location. We prototyped this design using software radios. Our empirical results with real satellite signals demonstrate that the new GPS receiver reduces the computational overhead by 2× to 6×, which translates into significant reduction in localization delay and power consumption. Chapter 8 presents the analysis and evaluation of the design in detail.
1.2.3 Light Field Photography
Light field photography is an active area in graphics where a 2D array of cameras or lenslets is used to capture the 4D light field of a scene.5 This enables a user to extract the 3D depth, refocus the scene to any plane, and change the angle from which he views the scene. This is essential for Virtual Reality (VR) systems as well as post processing of images and videos. Capturing light fields, however, is costly since it requires many cameras or lenslets to sample the scene from different viewpoints.
Thus, our goal is to reduce the cost of light field capture by using only few of the cameras in the 2D array and reconstructing the images from the missing cameras. To do this, we leverage the fact that the 4D Fourier transform of a light field is sparse and we use the Sparse Fourier Transform to subsample the input and reduce the number of cameras. Once we have computed the Fourier transform, we can invert it back to recover the images from the missing cameras which were not sampled and hence recover the full 2D array. However, as explained earlier, natural signals like light fields are not very sparse in the discrete domain. To address this issue, we developed a light field reconstruction system that optimizes for sparsity in the continuous Fourier domain. This improves the quality of reconstruction while reducing the required number of cameras by 6× to 10×. The light field reconstruction algorithm along with the reconstruction results can be found in
