18 research outputs found
Distributed scalar quantization for computing: High-resolution analysis and extensions
No full textCommunication of quantized information is frequently followed by a computation. We consider situations of distributed functional scalar quantization: distributed scalar quantization of (possibly correlated) sources followed by centralized computation of a function. Under smoothness conditions on the sources and function, companding scalar quantizer designs are developed to minimize mean-squared error (MSE) of the computed function as the quantizer resolution is allowed to grow. Striking improvements over quantizers designed without consideration of the function are possible and are larger in the entropy-constrained setting than in the fixed-rate setting. As extensions to the basic analysis, we characterize a large class of functions for which regular quantization suffices, consider certain functions for which asymptotic optimality is achieved without arbitrarily fine quantization, and allow limited collaboration between source encoders. In the entropy-constrained setting, a single bit per sample communicated between encoders can have an arbitrarily large effect on functional distortion. In contrast, such communication has very little effect in the fixed-rate setting.National Science Foundation (U.S.) (Grant 0729069
Functional quantization
No full textThesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.Includes bibliographical references (p. 119-121).Data is rarely obtained for its own sake; oftentimes, it is a function of the data that we care about. Traditional data compression and quantization techniques, designed to recreate or approximate the data itself, gloss over this point. Are performance gains possible if source coding accounts for the user's function? How about when the encoders cannot themselves compute the function? We introduce the notion of functional quantization and use the tools of high-resolution analysis to get to the bottom of this question. Specifically, we consider real-valued raw data Xn/1 and scalar quantization of each component Xi of this data. First, under the constraints of fixed-rate quantization and variable-rate quantization, we obtain asymptotically optimal quantizer point densities and bit allocations. Introducing the notions of functional typicality and functional entropy, we then obtain asymptotically optimal block quantization schemes for each component. Next, we address the issue of non-monotonic functions by developing a model for high-resolution non-regular quantization. When these results are applied to several examples we observe striking improvements in performance.Finally, we answer three questions by means of the functional quantization framework: (1) Is there any benefit to allowing encoders to communicate with one another? (2) If transform coding is to be performed, how does a functional distortion measure influence the optimal transform? (3) What is the rate loss associated with a suboptimal quantizer design? In the process, we demonstrate how functional quantization can be a useful and intuitive alternative to more general information-theoretic techniques.by Vinith Misra.M.Eng
Byzantine faulty operation recovery and cost analysis of SPURT: A distributed randomness beacon
No full textA reliable source of randomness plays an integral part in the design of many cryptographic, security, and distributed system protocols. Yet, existing constructions of distributed random beacons still have limitations such as strong setup or network assumptions, and high computational and communication costs. SPURT a novel efficient distributed randomness beacon protocol does not require any trusted or expensive setup and is secure against a malicious adversary that controls up to one-third of the nodes in a partially synchronous network. One crucial property that SPURT guarantees is unpredictability, which ensures that every honest party is able to recover the random beacon value either before or soon (3 single trip message delays) after the adversary recovers it. This thesis presents the recovery mechanisms that let SPURT provide the above guarantee even in the presence of a malicious leader. We implement SPURT and evaluate it using a network of up to 128 nodes running in geographically distributed AWS instances. Analysis and experiments demonstrated that SPURT offers very high throughput, while only incurring reasonable overhead costs from the recovery mechanisms.Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01The student, Vinith Krishnan, accepted the attached license on 2021-04-21 at 17:08.The student, Vinith Krishnan, submitted this Thesis for approval on 2021-04-21 at 17:15.This Thesis was approved for publication on 2021-04-23 at 16:46.DSpace SAF Submission Ingestion Package generated from Vireo submission #16480 on 2021-09-16 at 17:04:30Made available in DSpace on 2021-09-17T02:34:42Z (GMT). No. of bitstreams: 2
KRISHNAN-THESIS-2021.pdf: 634412 bytes, checksum: 74ca5ba6aca2738a27085a4c579de072 (MD5)
LICENSE.txt: 4212 bytes, checksum: c878f79dc3986ec827dbbec9c8c27670 (MD5)
Previous issue date: 2021-04-23Embargo set by: Seth Robbins for item 118563
Lift date: 2023-09-17T02:34:57Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemAuthor requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemU of I Onl
Ultralow-Power Electronics for Cardiac Monitoring
No full textUltralow-power electronics for cardiac monitoring make possible the development of new light-weight and low-cost devices that are ideal for long-term medical measurements and home-based tele-monitoring services. Nowadays, these devices are seen as a critical technology for reducing health-care costs. In this paper, we present several methods for reducing power consumption while retaining the precision necessary for cardiac monitoring. In particular, we describe a micropower electrocardiograph, an ultralow-power pulse oximeter, an ultralow-power phonocardiograph, an integrated-circuit switched-capacitor model of the heart, and an ultracompact and efficient lithium-ion battery charger. These components are, to our knowledge, currently the most power-efficient or minimal-size designs present in the literature in each respective category
Bernoulli Embeddings for Graphs
No full textJust as semantic hashing can accelerate information retrieval, binary valued embeddings can significantly reduce latency in the retrieval of graphical data. We introduce a simple but effective model for learning such binary vectors for nodes in a graph. By imagining the embeddings as independent coin flips of varying bias, continuous optimization techniques can be applied to the approximate expected loss. Embeddings optimized in this fashion consistently outperform the quantization of both spectral graph embeddings and various learned real-valued embeddings, on both ranking and pre-ranking tasks for a variety of datasets
Distributed functional scalar quantization simplified
No full textDistributed functional scalar quantization (DFSQ) theory provides optimality conditions and predicts performance of data acquisition systems in which a computation on acquired data is desired. We address two limitations of previous works: prohibitively expensive decoder design and a restriction to source distributions with bounded support. We show that a much simpler decoder has equivalent asymptotic performance to the conditional expectation estimator studied previously, thus reducing decoder design complexity. The simpler decoder features decoupled communication and computation blocks. Moreover, we extend the DFSQ framework with the simpler decoder to source distributions with unbounded support. Finally, through simulation results, we demonstrate that performance at moderate coding rates is well predicted by the asymptotic analysis, and we give new insight on the rate of convergence.First author draf
A micropower electrocardiogram amplifier
No full textWe introduce an electrocardiogram (EKG) preamplifier with a power consumption of 2.8 muW, 8.1 muV[subscript rms] input-referred noise, and a common-mode rejection ratio of 90 dB. Compared to previously reported work, this amplifier represents a significant reduction in power with little compromise in signal quality. The improvement in performance may be attributed to many optimizations throughout the design including the use of subthreshold transistor operation to improve noise efficiency, gain-setting capacitors versus resistors, half-rail operation wherever possible, optimal power allocations among amplifier blocks, and the sizing of devices to improve matching and reduce noise. We envision that the micropower amplifier can be used as part of a wireless EKG monitoring system powered by rectified radio-frequency energy or other forms of energy harvesting like body vibration and body heat.electrocardiogram (EKG
