Browsing by Subject "Compressive sensing"
Now showing 1 - 8 of 8
- Results Per Page
- Sort Options
Item A compressive sensing approach to solving nonograms(2013-05) Lopez, Oscar Fabian; Ward, Rachel, 1983-A nonogram is a logic puzzle where one shades certain cells of a 2D grid to reveal a hidden image. One uses the sequences of numbers on the left and the top of the grid to figure out how many and which cells to shade. We propose a new technique to solve a nonogram using compressive sensing. Our method avoids (1) partial fill-ins, (2) heuristics, and (3) over-complication, and only requires that we solve a binary integer programming problem.Item Efficient, provably secure code constructions(2011-05) Agrawal, Shweta Prem; Vishwanath, Sriram; Boneh, Dan; Zuckerman, David; Garg, Vijay; Caramanis, Constantine; Sanghavi, SujayThe importance of constructing reliable and efficient methods for securing digital information in the modern world cannot be overstated. The urgency of this need is reflected in mainstream media--newspapers and websites are full of news about critical user information, be it credit card numbers, medical data, or social security information, being compromised and used illegitimately. According to news reports, hackers probe government computer networks millions of times a day, about 9 million Americans have their identities stolen each year and cybercrime costs large American businesses 3.8 million dollars a year. More than 1 trillion worth of intellectual property has already been stolen from American businesses. It is this evergrowing problem of securing valuable information that our thesis attempts to address (in part). In this thesis, we study methods to secure information that are fast, convenient and reliable. Our overall contribution has four distinct threads. First, we construct efficient, "expressive" Public Key Encryption systems (specifically, Identity Based Encryption systems) based on the hardness of lattice problems. In Identity Based Encryption (IBE), any arbitrary string such as the user's email address or name can be her public key. IBE systems are powerful and address several problems faced by the deployment of Public Key Encryption. Our constructions are secure in the standard model. Next, we study secure communication over the two-user interference channel with an eavesdropper. We show that using lattice codes helps enhance the secrecy rate of this channel in the presence of an eavesdropper. Thirdly, we analyze the security requirements of network coding. Network Coding is an elegant method of data transmission which not only helps achieve capacity in several networks, but also has a host of other benefits. However, network coding is vulnerable to "pollution attacks" when there are malicious users in the system. We design mechanisms to prevent pollution attacks. In this setting, we provide two constructions -- a homomorphic Message Authentication Code (HMAC) and a Digital Signature, to secure information that is transmitted over such networks. Finally, we study the benefits of using Compressive Sensing for secure communication over the Wyner wiretap channel. Compressive Sensing has seen an explosion of interest in the last few years with its elegant mathematics and plethora of applications. So far however, Compressive Sensing had not found application in the domain of secrecy. Given its inherent assymetry, we ask (and answer in the affirmative) the question of whether it can be deployed to enable secure communication. Our results allow linear encoding and efficient decoding (via LASSO) at the legitimate receiver, along with infeasibility of message recovery (via an information theoretic analysis) at the eavesdropper, regardless of decoding strategy.Item Fully-passive switched-capacitor techniques for high performance SAR ADC design(2016-02-11) Guo, Wenjuan, Ph. D. in electrical and computer engineering; Sun, Nan; Orshansky, Michael; Tewfik, Ahmed H.; Viswanathan, T. R.In recent years, SAR ADC becomes more and more popular in various low-power applications such as wireless sensors and low energy radios due to its circuit simplicity, high power efficiency, and scaling compatibility. However, its speed is limited by its successive approximation procedures and its power efficiency greatly reduces with the ADC resolution going beyond 10 bit. To address these issues, this thesis proposes to embed two techniques: 1) compressive sensing (CS) and 2) noise shaping (NS) to a conventional SAR ADC. The realization of both techniques are based on fully-passive switched-capacitor techniques. CS is a recently emerging sampling paradigm, stating that the sparsity of a signal can be exploited to reduce the ADC sampling rate below the Nyquist rate. Different from conventional CS frameworks which require dedicated analog CS encoders, this thesis proposes a fully-passive CS-SAR ADC architecture which only requires minor modification to a conventional SAR ADC. Two chips are fabricated in a 0.13 µm process to prove the concept. One chip is a single-channel CS-SAR ADC which can reduce the ADC conversion rate by 4 times, thus reducing the ADC power by 4 times. In many wireless sensing applications, multiple ADCs are commonly required to sense multi-channel signals such as multi-lead ECG sensing and parallel neural recording. Therefore, the other chip is a multi-channel CS-SAR ADC which can simultaneously convert 4-channel signals with a sampling rate of one channel’s Nyquist rate. At 0.8 V and 1 MS/s, both chips achieve an effective Walden FoM of around 5 fJ/conversion-step. This thesis also proposes a novel NS SAR ADC architecture that is simple, robust and low power for high-resolution applications. Compared to conventional ∆Σ ADCs, it replaces the power-hungry active integrator with a passive integrator which only requires one switch and two capacitors. Compared to previous 1st-order NS SAR ADC works, it achieves the best NS performance and can be easily extended to 2nd-order. A 1st-order 10-bit NS SAR ADC is fabricated in a 0.13 µm process. Through NS, SNDR increases by 6 dB with OSR doubled, achieving a 12- bit ENOB at OSR = 8. An improved version of a 2nd-order 9-bit NS SAR ADC is designed and simulated in a 40 nm process. The SNDR increases by 10 dB with OSR doubled, achieving a 14-bit ENOB at OSR = 16. At a bandwidth of 312.5 kHz, the Schreier FoM is 181 dB and the Walden FoM is 12.5 fJ/conversion-step, proving that the proposed NS SAR ADC architecture can achieve high resolution and high power efficiency simultaneously.Item Hybrid analog/digital MIMO architecture in large antenna array systems(2018-12) Park, Sungwoo, Ph. D.; Heath, Robert W., Jr., 1973-; Andrews, Jeffrey G.; Caramanis, Constantine; Vikalo, Haris; González-Prelcic, NuriaHybrid analog/digital precoding architectures can address the trade-off between achievable spectral efficiency and power consumption in large-scale multiple-input-multiple-output (MIMO) systems. This feature makes the hybrid precoding a promising candidate for millimeter wave systems and massive MIMO systems, which deploy large antenna arrays. One of the major problems with prior work on hybrid architecture is that conventional hybrid precoding methods require full channel state information (CSI), which is difficult to obtain in particular when the hybrid architecture is employed. In the first two contributions of this dissertation, hybrid precoding design methods that require spatial channel covariance information instead of instantaneous full CSI are proposed for the analog part design. Hybrid precoding design with spatial channel covariance for single-user MIMO (SU-MIMO) and multiuser MIMO (MU-MIMO) are proposed in the first and second contribution. Both theoretical and numerical analysis demonstrate that the spatial channel covariance can replace instantaneous full CSI with marginal rate loss for spatially sparse channels. Spatial channel covariance estimation, however, is challenging for the hybrid MIMO architecture because the estimator operating at baseband can only obtain a lower dimensional pre-combined signal through fewer radio frequency (RF) chains than antennas. This challenging task is tackled in the last two contributions. In the third contribution, compressive sensing techniques are applied to spatial channel covariance estimation over time-varying frequency-at channels by exploiting the channel sparsity. Taking time-varying frequency-selective channels into consideration, higher-order tensor decomposition techniques are adopted in the fourth contribution. Simulation and analytical results envince that the proposed methods estimate the spatial channel covariance more accurately and more quickly compared to prior workItem Low power sensor readout circuit design for IoT applications(2020-07-07) Zhao, Wenda; Sun, Nan; Pan, Zhigang; Orshansky, Michael; Lu, Nanshu; Chae, YoungcheolEnergy and area-efficient sensor readouts have drawn increasing attention in the integrated circuit design field as the entering of the Internet-of-Things (IoT) era. Small form factor and extended battery life have become critical design targets as important as conventional analog and mixed-signal sensor readout specifications such as noise and dynamic range (DR). Technology advancement has brought extensive benefits to digital circuits, but analog circuits have been facing great design challenges due to the voltage supply and transistor intrinsic gain reduction in advanced processes. This presents a strong need for new design frameworks for sensor readouts that can leverage the properties of CMOS scaling instead of being limited by them. On the other hand, for sensor applications where multiple ADCs are required for multi-channel or parallel signal acquisition, the existence of a large number of ADCs usually causes area and power to grow linearly with the number of ADCs. For those applications, analog compression presents a great potential to become a valuable solution to further improve energy efficiency for sensor readouts on top of the advanced circuit design techniques. To address the challenges brought by the era of IoT, this dissertation explores solutions for IoT sensor readouts from two directions: area-/energy-efficient phase-domain VCO-based sensor readout circuit for single-channel general-purpose sensor interface and compressive sensing (CS) based analog compression scheme and readout circuits for multi-channel sensing scenarios. The first work presents a capacitively-coupled voltage-controlled oscillator (VCO)-based sensor readout featuring a hybrid phase-locked loop (PLL) - [Delta-Sigma] modulator structure. This work aims to propose a solution to the issues of analog sensor readout in advanced processes. It leverages phase-locking and phase-frequency detector (PFD) array to concurrently perform quantization and dynamic element matching (DEM), much reducing hardware/power compared to existing VCO-based readouts' counting scheme. A low-cost in-cell data weighted averaging (DWA) scheme is presented to enable highly linear tri-level digital-to-analog converter (DAC). Fabricated in 40 nm CMOS, the prototype readout achieves 78 dB SNDR in 10 kHz bandwidth, consuming 4.68 µW and 0.025 mm² active area. With 172 dB Schreier FoM, its efficiency advances state-of-the-art VCO-based readouts by 50 times. The second work presents a 4x compressive CMOS image sensor for always-on operation that achieves an energy efficiency of 51 pJ/pixel, while maintaining high image quality of PSNR > 32dB and SSIM > 0.84. This is enabled by an energy-efficient CS encoder, which replaces a densely populated CS encoding method with a highly sparse pseudo-diagonal one. Since the proposed CS encoder can be implemented with an energy-efficient switched-capacitor matrix multiplier at pixel outputs, data compression is achieved before to pixel digitization, thereby greatly reducing ADC power, data size, and I/O power. The energy efficiency of the image sensor is further improved by incorporating it into dynamic single-slope ADCs. A prototype VGA image sensor consumes only 0.7 mW at 45 fps. The corresponding energy per pixel (51 pJ/pixel) amounts to a 20x improvement over the previous low-energy benchmark on CS image sensors.Item Mobile localization : approach and applications(2014-12) Rallapalli, Swati; Qiu, Lili, Ph. D.Localization is critical to a number of wireless network applications. In many situations GPS is not suitable. This dissertation (i) develops novel localization schemes for wireless networks by explicitly incorporating mobility information and (ii) applies localization to physical analytics i.e., understanding shoppers' behavior within retail spaces by leveraging inertial sensors, Wi-Fi and vision enabled by smart glasses. More specifically, we first focus on multi-hop mobile networks, analyze real mobility traces and observe that they exhibit temporal stability and low-rank structure. Motivated by these observations, we develop novel localization algorithms to effectively capture and also adapt to different degrees of these properties. Using extensive simulations and testbed experiments, we demonstrate the accuracy and robustness of our new schemes. Second, we focus on localizing a single mobile node, which may not be connected with multiple nodes (e.g., without network connectivity or only connected with an access point). We propose trajectory-based localization using Wi-Fi or magnetic field measurements. We show that these measurements have the potential to uniquely identify a trajectory. We then develop a novel approach that leverages multi-level wavelet coefficients to first identify the trajectory and then localize to a point on the trajectory. We show that this approach is highly accurate and power efficient using indoor and outdoor experiments. Finally, localization is a critical step in enabling a lot of applications --- an important one is physical analytics. Physical analytics has the potential to provide deep-insight into shoppers' interests and activities and therefore better advertisements, recommendations and a better shopping experience. To enable physical analytics, we build ThirdEye system which first achieves zero-effort localization by leveraging emergent devices like the Google-Glass to build AutoLayout that fuses video, Wi-Fi, and inertial sensor data, to simultaneously localize the shoppers while also constructing and updating the product layout in a virtual coordinate space. Further, ThirdEye comprises of a range of schemes that use a combination of vision and inertial sensing to study mobile users' behavior while shopping, namely: walking, dwelling, gazing and reaching-out. We show the effectiveness of ThirdEye through an evaluation in two large retail stores in the United States.Item Recovery of continuous quantities from discrete and binary data with applications to neural data(2014-12) Knudson, Karin Comer; Ward, Rachel. 1983-; Pillow, Jonathan W.We consider three problems, motivated by questions in computational neuroscience, related to recovering continuous quantities from binary or discrete data or measurements in the context of sparse structure. First, we show that it is possible to recover the norms of sparse vectors given one-bit compressive measurements, and provide associated guarantees. Second, we present a novel algorithm for spike-sorting in neural data, which involves recovering continuous times and amplitudes of events using discrete bases. This method, Continuous Orthogonal Matching Pursuit, builds on algorithms used in compressive sensing. It exploits the sparsity of the signal and proceeds greedily, achieving gains in speed and accuracy over previous methods. Lastly, we present a Bayesian method making use of hierarchical priors for entropy rate estimation from binary sequences.Item Robust network compressive sensing(2015-12) Chen, Yi-Chao, Ph. D.; Qiu, Lili, Ph. D.; Lam, Simon; Lee, Sung-Ju; Mok, Aloysius; Ravikumar, PradeepNetworks are constantly generating an enormous amount of rich and diverse information. Such information creates exciting opportunities for network analytics and provides deep insights into the complex interactions among network entities. However, network analytics often faces the problem of (i) under-constraint, where there is too little data due to the feasibility/cost of collecting data; or (ii) over-constraint, where there is too much data so the analytics becomes unscalable. Compressive sensing is an effective technique to solve both problems. It leverages the underlying data structure for analysis. To address the under-constraint problem, we can apply compressive sensing to reconstruct missing elements or predict future data. To address the over-constraint problem, we can apply compressive sensing to identify important factors. Compressive sensing has many applications. In the thesis, we apply compressive sensing to missing data interpolation, anomaly detection, data segmentation, and activity recognition and show their benefit. To demonstrate the feasibility of compressive sensing in network analytics, we first apply it to detect anomalies in a customer care call dataset. Customer care call dataset is collected by a tier-1 ISP in US and includes the calls which are labeled as categories representing customers' problems. Customer care calls reveal the major events and problems observed by customers. We use a regression-based approach to find the relationship between calls and events. We show that compressive sensing is effective in identifying important factors and can leverage the low-rank structure and temporal stability of the data to improve the detection accuracy. While applying compressive sensing to the real-world data, we identify several challenges. One of the challenges is that real-world data are complicated and heterogeneous, and often violate the low-rank assumption required by existing compressive sensing techniques. Such violation significantly reduces the applicability and effectiveness of existing compressive sensing approaches. It is important to understand reasons behind the violation to design methods and mitigate the impact. Therefore, we analyze a wide range of real-world traces and our analysis reveals that there are different factors that contribute to the violation of low-rank property in real data. In particular, we find (i) noise, errors, anomalies, and (ii) the lack of synchronization in time and frequency-domain lead to network-induced blurring, and can easily cause a low-rank matrix to become a much higher rank. To address the problem of noise, errors, and anomalies, we present a robust compressive sensing technique. It explicitly account for anomalies by decomposing real-world data represented in the form of a matrix into a low-rank matrix, a sparse anomaly matrix, an error term, and a small noise matrix. To address the problem of the lack of synchronization, we present a data-driven synchronization algorithm. It removes misalignment while accounting for the time and frequency-domain heterogeneity in the real-world data. The data-driven synchronization can be applied to any compressive sensing technique and is general for any real-world trace. We show that the combination of two techniques can reduce the ranks of the real-world data, improve the effectiveness of compressive sensing, and have a wide range of applications.