Search

We present the first known implementation of elliptic curve cryptography over F2p for sensor networks based on the 8-bit, 7.3828-MHz MICA2 mote. Through instrumentation of UC Berkeley's TinySec module, we argue that, although secret-key cryptography has been tractable in this domain for some time, there has remained a need for an efficient, secure mechanism for distribution of secret keys among nodes. Although public-key infrastructure has been thought impractical, we argue, through analysis of our own implementation for TinyOS of multiplication of points on elliptic curves, that public-key infrastructure is, in fact, viable for TinySec keys' distribution, even on the MICA2. We demonstrate that public keys can be generated within 34 seconds, and that shared secrets can be distributed among nodes in a sensor network within the same, using just over 1 kilobyte of SRAM and 34 kilobytes of ROM., Engineering and Applied Sciences

This paper presents a novel approach to analyze the shape of anatomical structures. Our methodology is rooted in classical physics and in particular Poisson's equation, a fundamental partial differential equation [1]. The solution to this equation and more specifically its equipotential surfaces display properties that are useful for shape analysis. We present a numerical algorithm to calculate the length of streamlines formed by the gradient field of the solution to this equation for 2D and 3D objects. The length of the streamlines along the equipotential surfaces was used to build a new function which can characterize the shape of objects. We illustrate our method on 2D synthetic and natural shapes as well as 3D medical data.

Although higher-order statistics of neuronal firing have been characterized in neuroscience, many analyses ignore the nonstationarity of the background firing rate. We discuss how to measure the irregularity of interspike intervals in a rate-independent manner. Under the framework of semiparametric statistical models, we develop an estimator of firing irregularity which remains after the effects of rate modulations are removed. We found that firing irregularity is robust and reproducible in neurons in olfactory cortex irrespective of the rate modulation during the task period. As the level of irregularity varies among neurons, we classified neurons in olfactory cortex by using the proposed measure as a feature., Molecular and Cellular Biology

We consider a wireless transmission scenario, when a base station is endowed with a fixed beamforming network, where M antennas are employed at the base station to point beams to predetermined azimuthal angles. In our setting, a Butler matrix is deployed at the RF stage to form M beams, and then the best beam is selected for transmission. We derive the distribution of the beam selection gain for this scenario under a Rician channel assumption as a function of both the azimuthal location of the remote unit and the Rician K-factor. Using some key properties of the noncentral chi-square distribution, we prove that beam selection outperforms manual antenna selection., Engineering and Applied Sciences

We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertions and deletions. This improves on prior results that obtain suboptimal space bounds in the general model, and near-optimal bounds in the insertion-only model without sketching. Our high-level approach is simple: we give algorithms to estimate Renyi and Tsallis entropy, and use them to extrapolate an estimate of Shannon entropy. The accuracy of our estimates is proven using approximation theory arguments and extremal properties of Chebyshev polynomials, a technique which may be useful for other problems. Our work also yields the best-known and near-optimal additive approximations for entropy, and hence also for conditional entropy and mutual information., Engineering and Applied Sciences

We present FlowCode, a system that exploits network coding at the granularity of traffic flows to facilitate fault-tolerant data exchange in wireless mesh networks. Applications include multi-site data replication in ad-hoc environments such as mesh networks or wireless data centers. By coupling an operand-driven transmission mechanism with a layered network topology, FlowCode allows us to realize the gains of network coding in application systems without a global scheduler. We analyze the resulting gains through modeling and simulation and validate our results on an outdoor testbed of 12 wireless devices. Results indicate that in high loss environments, FlowCode provides the most significant gains from improved fault tolerance over redundant paths., Engineering and Applied Sciences

This paper presents a model of collaborative decision-making for groups that involve people and computer agents. The model distinguishes between actions relating to participantspsila commitment to the group and actions relating to their individual tasks, uses this distinction to decompose group decision making into smaller problems that can be solved efficiently. It allows computer agents to reason about the benefits of their actions on a collaboration and the ways in which human participants perceive these benefits. The model was tested in a setting in which computer agents need to decide whether to interrupt people to obtain potentially valuable information. Results show that the magnitude of the benefit of interruption to the collaboration is a major factor influencing the likelihood that people will accept interruption requests. They further establish that peoplepsilas perceived type of their partners (whether humans or computers) significantly affected their perceptions of the usefulness of interruptions when the benefit of the interruption is not clear-cut. These results imply that system designers need to consider not only the possible benefits of interruptions to collaborative human-computer teams but also the way that such benefits are perceived by people., Engineering and Applied Sciences

In this paper, we use a finite-state model to predict the performance of the Transmission Control Protocol (TCP) over a varying wireless channel between an unmanned aerial vehicle (UAV) and ground nodes. As a UAV traverses its flight path, the wireless channel may experience periods of significant packet loss, successful packet delivery, and intermittent reception. By capturing packet run-length and gap-length statistics at various locations on the flight path, this location-dependent model can predict TCP throughput in spite of dynamically changing channel characteristics. We train the model by using packet traces from flight tests in the field and validate it by comparing TCP throughput distributions for model-generated traces against those for actual traces randomly sampled from field data. Our modeling methodology is general and can be applied to any UAV flight path., Engineering and Applied Sciences

For an n-variate degree-2 real polynomial p, we prove that \(E_{x\sim D}[sig(p(x))]\) Is determined up to an additive \(\epsilon\) as long as D is a k-wise Independent distribution over \(\{-1, 1\}^n\) for \(k = poly(1/\epsilon)\). This gives a broad class of explicit pseudorandom generators against degree-2 boolean threshold functions, and answers an open question of Diakonikolas et al. (FOCS 2009)., Engineering and Applied Sciences

We consider the problem of mitigating a highly varying wireless channel between a transmitting ground node and receivers on a small, low-altitude unmanned aerial vehicle (UAV) in a 802.11 wireless mesh network. One approach is to use multiple transmitter and receiver nodes that exploit the channel's spatial/temporal diversity and that cooperate to improve overall packet reception. We present a series of measurement results from a real-world testbed that characterize the resulting wireless channel. We show that the correlation between receiver nodes on the airplane is poor at small time scales so receiver diversity can be exploited. Our measurements suggest that using several receiver nodes simultaneously can boost packet delivery rates substantially. Lastly, we show that similar results apply to transmitter selection diversity as well., Engineering and Applied Sciences

A novel approach to constructing robots is based on concentrically combining pre-curved elastic tubes. By rotating and extending the tubes with respect to each other, their curvatures interact elastically to position and orient the robot's tip, as well as to control the robot's shape along its length. Since these robots form slender curves, they are well suited for minimally invasive medical procedures. A substantial challenge to their practical use is the real-time solution of their kinematics that are described by differential equations with split boundary equations. This paper proposes a numerically efficient approach to real-time position control. It is shown that the forward kinematics are smooth functions that can be pre-computed and accurately approximated using Fourier series. The inverse kinematics can be solved in real time using root finding applied to the functional approximation. Experimental demonstration of real-time position control using this approach is also described.

Large collections of robots have the potential to perform tasks collectively using distributed control algorithms. These algorithms require communication between robots to allow the robots to coordinate their behavior and act as a collective. In this paper we describe two algorithms which allow coordination between robots, but do not require physical environment marks such as pheromones. Instead, these algorithms rely on simple, local, low bandwidth, direct communication between robots. We describe the algorithms and measure their performance in worlds with and without obstacles., Engineering and Applied Sciences

Wireless data transfer under high mobility, as found in unmanned aerial vehicle (UAV) applications, is a challenge due to varying channel quality and extended link outages. We present FlowCode, an easily deployable link-layer solution utilizing multiple transmitters and receivers for the purpose of supporting existing transport protocols such as TCP in these scenarios. By using multiple transmitters and receivers and by exploiting the resulting antenna beam diversity and parallel transmission effects, FlowCode increases throughput and reception range. In emulation, we show that TCP over FlowCode gives greater goodput over a larger portion of the flight path, compared to an enhanced TCP protocol using the standard 802.11 MAC. In the process, we make a strong case for using trace-modulated emulation when developing distributed protocols for complex wireless environments., Engineering and Applied Sciences

We propose a novel systematic approach to optimizing the design of concentric tube robots for neurosurgical procedures. These procedures require that the robot approach specified target sites while navigating and operating within an anatomically constrained work space. The availability of preoperative imaging makes our approach particularly suited for neurosurgery, and we illustrate the method with the example of endoscopic choroid plexus ablation. A novel parameterization of the robot characteristics is used in conjunction with a global pattern search optimization method. The formulation returns the design of the least-complex robot capable of reaching single or multiple target points in a confined space with constrained optimization metrics. A particular advantage of this approach is that it identifies the need for either fixed-curvature versus variable-curvature sections. We demonstrate the performance of the method in four clinically relevant examples.

Three-dimensional ultrasound can be an effective imaging modality for image-guided interventions since it enables visualization of both the instruments and the tissue. For robotic applications, its realtime frame rates create the potential for image-based instrument tracking and servoing. These capabilities can enable improved instrument visualization, compensation for tissue motion as well as surgical task automation. Continuum robots, whose shape comprises a smooth curve along their length, are well suited for minimally invasive procedures. Existing techniques for ultrasound tracking, however, are limited to straight, laparoscopic-type instruments and thus are not applicable to continuum robot tracking. Toward the goal of developing tracking algorithms for continuum robots, this paper presents a method for detecting a robot comprised of a single constant curvature in a 3D ultrasound volume. Computational efficiency is achieved by decomposing the six-dimensional circle estimation problem into two sequential three-dimensional estimation problems. Simulation and experiment are used to evaluate the proposed method.

To determine object geometry in unstructured environments, sensors must be mechanically robust, must exert only low forces on objects during exploration, and must be able to scan large regions efficiently without risk of damaging objects or sensors. Joint-angle sensors on compliant joints provide an appealing option for this task. An algorithmic framework is presented that allows them to be used for contact detection and to determine object geometry without requiring tactile arrays or other complicated contact location sensors. This volumetric approach to using proprioceptive sensors provides improvements in accuracy over other existing approaches based on the intersection of planes and lines., Engineering and Applied Sciences

We describe a set of image editing and viewing tools that explicitly take into account the resolution of the display on which the image is viewed. Our approach is twofold. First, we design editing tools that process only the visible data, which is useful for images larger than the display. This encompasses cases such as multi-image panoramas and high-resolution medical data. Second, we propose an adaptive way to set viewing parameters such brightness and contrast. Because we deal with very large images, different locations and scales often require different viewing parameters. We let users set these parameters at a few places and interpolate satisfying values everywhere else. We demonstrate the efficiency of our approach on different display and image sizes. Since the computational complexity to render a view depends on the display resolution and not the actual input image resolution, we achieve interactive image editing even on a 16 gigapixel image., Engineering and Applied Sciences

We present two theses in this paper: First, performance of most existing face recognition algorithms improves if instead of the whole image, smaller patches are individually classified followed by label aggregation using voting. Second, weighted plurality voting outperforms other popular voting methods if the weights are set such that they maximize the victory margin for the winner with respect to each of the losers. Moreover, this can be done while taking higher order relationships among patches into account using kernels. We call this scheme Kernel Plurality. We verify our proposals with detailed experimental results and show that our framework with Kernel Plurality improves the performance of various face recognition algorithms beyond what has been previously reported in the literature. Furthermore, on five different benchmark datasets - Yale A, CMU PIE, MERL Dome, Extended Yale B and Multi-PIE, we show that Kernel Plurality in conjunction with recent face recognition algorithms can provide state-of-the-art results in terms of face recognition rates., Engineering and Applied Sciences

This paper presents a novel actuation technology for robotically assisted MRI-guided interventional procedures. Compact and wireless, the actuators are both powered and controlled by the MRI scanner. The design concept and performance limits are described and derived analytically. Simulation and experiments in a clinical MR scanner are used to validate the analysis and to demonstrate the capability of the approach for needle biopsies. The concepts of actuator locking mechanisms and multi-axis control are also introduced.

Surgical repair of the mitral valve is a difficult procedure that is often avoided in favor of less effective valve replacement because of the associated technical challenges facing non-expert surgeons. In the interest of increasing the rate of valve repair, an accurate, interactive surgical simulator for mitral valve repair was developed. With a haptic interface, users can interact with a mechanical model during simulation to aid in the development of a surgical plan and then virtually implement the procedure to assess its efficacy. Sub-millimeter accuracy was achieved in a validation study, and the system was successfully used by a cardiac surgeon to repair three virtual pathological valves., Engineering and Applied Sciences

We address the problem of automatic 3D segmentation of a stack of electron microscopy sections of brain tissue. Unlike previous efforts, where the reconstruction is usually done on a section-to-section basis, or by the agglomerative clustering of 2D segments, we leverage information from the entire volume to obtain a globally optimal 3D segmentation. To do this, we formulate the segmentation as the solution to a fusion problem. We first enumerate multiple possible 2D segmentations for each section in the stack, and a set of 3D links that may connect segments across consecutive sections. We then identify the fusion of segments and links that provide the most globally consistent segmentation of the stack. We show that this two-step approach of pre-enumeration and posterior fusion yields significant advantages and provides state-of-the-art reconstruction results. Finally, as part of this method, we also introduce a robust rotationally-invariant set of features that we use to learn and enumerate the above 2D segmentations. Our features outperform previous connectomic-specific descriptors without relying on a large set of heuristics or manually designed filter banks., Engineering and Applied Sciences

We propose an approach for cross-view action recognition by way of ‘virtual views’ that connect the action descriptors extracted from one (source) view to those extracted from another (target) view. Each virtual view is associated with a linear transformation of the action descriptor, and the sequence of transformations arising from the sequence of virtual views aims at bridging the source and target views while preserving discrimination among action categories. Our approach is capable of operating without access to labeled action samples in the target view and without access to corresponding action instances in the two views, and it also naturally incorporate and exploit corresponding instances or partial labeling in the target view when they are available. The proposed approach achieves improved or competitive performance relative to existing methods when instance correspondences or target labels are available, and it goes beyond the capabilities of these methods by providing some level of discrimination even when neither correspondences nor target labels exist., Engineering and Applied Sciences

Consumer digital cameras use tone-mapping to produce compact, narrow-gamut images that are nonetheless visually pleasing. In doing so, they discard or distort substantial radiometric signal that could otherwise be used for computer vision. Existing methods attempt to undo these effects through deterministic maps that de-render the reported narrow-gamut colors back to their original wide-gamut sensor measurements. Deterministic approaches are unreliable, however, because the reverse narrow-to-wide mapping is one-to-many and has inherent uncertainty. Our solution is to use probabilistic maps, providing uncertainty estimates useful to many applications. We use a non-parametric Bayesian regression technique - local Gaussian process regression - to learn for each pixel's narrow-gamut color a probability distribution over the scene colors that could have created it. Using a variety of consumer cameras we show that these distributions, once learned from training data, are effective in simple probabilistic adaptations of two popular applications: multi-exposure imaging and photometric stereo. Our results on these applications are better than those of corresponding deterministic approaches, especially for saturated and out-of-gamut colors., Engineering and Applied Sciences

The rapidly evolving landscape of multicore architectures makes the construction of efficient libraries a daunting task. A family of methods known collectively as “auto-tuning” has emerged to address this challenge. Two major approaches to auto-tuning are empirical and model-based: empirical autotuning is a generic but slow approach that works by measuring runtimes of candidate implementations, model-based auto-tuning predicts those runtimes using simplified abstractions designed by hand. We show that machine learning methods for non-linear regression can be used to estimate timing models from data, capturing the best of both approaches. A statistically-derived model offers the speed of a model-based approach, with the generality and simplicity of empirical auto-tuning. We validate our approach using the filterbank correlation kernel described in Pinto and Cox [2012], where we find that 0.1 seconds of hill climbing on the regression model (“predictive auto-tuning”) can achieve almost the same speed-up as is brought by minutes of empirical auto-tuning. Our approach is not specific to filterbank correlation, nor even to GPU kernel auto-tuning, and can be applied to almost any templated-code optimization problem, spanning a wide variety of problem types, kernel types, and platforms., Engineering and Applied Sciences, Molecular and Cellular Biology

We have assembled a tiled array \((220 cm^2)\) of fine pixel (0.6 mm) imaging CZT detectors for a balloon borne widefield hard X-ray telescope, ProtoEXIST2. ProtoEXIST2 is a prototype experiment for a next generation hard X-ray imager MlRAX-HXI on board Lattes, a spacecraft from the Agencia Espacial Brasilieira. MlRAX will survey the 5 to 200 keV sky of Galactic bulge, adjoining southern Galactic plane and the extragalactic sky with 6' angular resolution. This survey will open a vast discovery space in timing studies of accretion neutron stars and black holes. The ProtoEXIST2 CZT detector plane consists of 64 of 5 mm thick 2cm × 2cm CZT crystals tiled with a minimal gap. MIRAX will consist of 4 such detector planes, each of which will be imaged with its own coded-aperture mask. We present the packaging architecture and assembly procedure of the ProtoEXIST2 detector. On 2012, Oct 10, we conducted a successful high altitude balloon experiment of the ProtoEXISTl and 2 telescopes, which demonstrates their technology readiness for space application. Both telescopes performed flawlessly during the flight as well as on the ground. We report the results of pre-flight ground calibration and the preliminary results for the detector performance in the balloon flight., Astronomy, Other Research Unit

As the rapid expansion of smart phones and associated data-intensive applications continues, we expect to see renewed interest in dynamic prioritization schemes as a way to increase the total utility of a heterogeneous user base, with each user experiencing variable demand and value for access. We adapt a recent sampled-based mechanism for resource allocation to this setting, which is more effective in aligning incentives in a setting with variable demand than an earlier method for pricing network resources due to Varian and Mackie-Mason (1994). Complementing our theoretical analysis, which also considers incentives on the sell-side of the market, we present the results of a simulation study, confirming the effectiveness of our protocol in aligning incentives and boosting welfare., Engineering and Applied Sciences

We introduce Competing Mobile Network Game (CMNG), a stochastic game played by cognitive radio networks that compete for dominating an open spectrum access. Differentiated from existing approaches, we incorporate both communicator and jamming nodes to form a network for friendly coalition, integrate antijamming and jamming subgames into a stochastic framework, and apply Q-learning techniques to solve for an optimal channel access strategy. We empirically evaluate our Q-learning based strategies and find that Minimax-Q learning is more suitable for an aggressive environment than Nash-Q while Friend-or-foe Q-learning can provide the best solution under distributed mobile ad hoc networking scenarios in which the centralized control can hardly be available., Engineering and Applied Sciences

For the famous Giza Pyramids, the Sphinx, and surrounding tombs and temples, just west of modern Cairo (3rd millennium BCE), the Giza Project at Harvard University is blending older traditional archives (dig photos, archaeological drawings, object metadata) with realistic 3D visualization of the site. This marriage of old and new provides revolutionary access to Giza, its statues, hieroglyphic inscriptions, architecture, and wall decoration. Real-time immersive models allow us to pose new research questions, provide interactive classroom instruction, and investigate diachronic approaches to Giza's evolution over several millennia., Anthropology

We build a data-driven hierarchical inference model to predict wireless link quality between a mobile unmanned aerial vehicle (UAV) and ground nodes. Clustering, sparse feature extraction, and non-linear pooling are combined to improve Support Vector Machine (SVM) classification when a limited training set does not comprehensively characterize data variations. Our approach first learns two layers of dictionaries by clustering packet reception data. These dictionaries are used to perform sparse feature extraction, which expresses link state vectors first in terms of a few prominent local patterns, or features, and then in terms of co-occurring features along the flight path. In order to tolerate artifacts like small positional shifts in field-collected data, we pool large magnitude features among overlapping shifted patches within windows. Together, these techniques transform raw link measurements into stable feature vectors that capture environmental effects driven by radio range limitations, antenna pattern variations, line-of-sight occlusions, etc. Link outage prediction is implemented by an SVM that assigns a common label to feature vectors immediately preceding gaps of successive packet losses, predictions are then fed to an adaptive link layer protocol that adjusts forward error correction rates, or queues packets during outages to prevent TCP timeout. In our harsh target environment, links are unstable and temporary outages common, so baseline TCP connections achieve only minimal throughput. However, connections under our predictive protocol temporarily hold packets that would otherwise be lost on unavailable links, and react quickly when the UAV link is restored, increasing overall channel utilization., Engineering and Applied Sciences

To study the emergence of cooperative behavior, we have developed a scalable parallel framework for evolutionary game dynamics. This is a critical computational tool enabling large-scale agent simulation research. An important aspect is the amount of history, or memory steps, that each agent can keep. When six memory steps are taken into account, the strategy space spans \(2^{4096}\) potential strategies, requiring large populations of agents. We introduce a multi-level decomposition method that allows us to exploit both multi-node and thread-level parallel scaling while minimizing communication overhead. We present the results of a production run modeling up to six memory steps for populations consisting of up to 1018 agents, making this study one of the largest yet undertaken. The high rate of mutation within the population results in a non-trivial parallel implementation. The strong and weak scaling studies provide insight into parallel scalability and programmability trade-offs for large-scale simulations, while exhibiting near perfect weak and strong scaling on 16,384 tasks on Blue Gene/Q. We further show 99% weak scaling up to 294,912 processors 82% strong scaling efficiency up to 262,144 processors of Blue Gene/P. Our framework marks an important step in the study of game dynamics with potential applications in fields ranging from biology to economics and sociology., Engineering and Applied Sciences

This paper describes an adaptation of cognitive radio technology for tactical wireless networking. We introduce Competing Cognitive Radio Network (CCRN) featuring both communicator and jamming cognitive radio nodes that strategize in taking actions on an open spectrum under the presence of adversarial threats. We present the problem in the Multi-armed Bandit (MAB) framework and develop the optimal media access strategy consisting of mixed communicator and jammer actions in a Bayesian setting for Thompson sampling based on extreme value theory. Empirical results are promising that the proposed strategy seems to outperform Lai & Robbins and UCB, some of the most important MAB algorithms known to date., Engineering and Applied Sciences

In wireless body area sensor networking (WBASN) applications such as gastrointestinal (GI) tract monitoring using wireless video capsule endoscopy (WCE), the performance of out-of-body wireless link propagating through different body media (i.e. blood, fat, muscle and bone) is still under investigation. Most of the localization algorithms are vulnerable to the variations of path-loss coefficient resulting in unreliable location estimation. In this paper, we propose a novel robust probabilistic Bayesian-based approach using received-signal-strength (RSS) measurements that accounts for Rayleigh fading, variable path-loss exponent and uncertainty in location information received from the neighboring nodes and anchors. The results of this study showed that the localization root mean square error of our Bayesian-based method was 1.6 mm which was very close to the optimum Cramer-Rao lower bound (CRLB) and significantly smaller than that of other existing localization approaches (i.e. classical MDS (64.2mm), dwMDS (32.2mm), MLE (36.3mm) and POCS (2.3mm))., Engineering and Applied Sciences

Recent advances in materials, devices and fabrication technologies have motivated a strong momentum in developing solid-state sensors that can detect individual photons in space and time. It has been envisioned that such sensors can eventually achieve very high spatial resolutions (e.g., \(10^9\) pixels/chip) as well as high frame rates (e.g., \(10^6\) frames/sec). In this paper, we present an efficient algorithm to reconstruct images from the massive binary bit-streams generated by these sensors. Based on the concept of alternating direction method of multipliers (ADMM), we transform the computationally intensive optimization problem into a sequence of subproblems, each of which has efficient implementations in the form of polyphase-domain filtering or pixel-wise nonlinear mappings. Moreover, we reformulate the original maximum likelihood estimation as maximum a posterior estimation by introducing a total variation prior. Numerical results demonstrate the strong performance of the proposed method, which achieves several dB’s of improvement in PSNR and requires a shorter runtime as compared to standard gradient-based approaches., Engineering and Applied Sciences

Solar geoengineering (or Solar Radiation Management, SRM) refers to any intentional, large-scale manipulation of the Earth's incoming solar radiation to offset some of the effects of anthropogenic greenhouse gases, reducing the associated risks from climate changes. Examples of such methods are injecting aerosols into the stratosphere or increasing marine cloud reflectivity, both of which would reflect some sunlight back to space. There are many serious concerns associated with any such approach, and also many challenges. One often overlooked aspect in geoengineering research is that this is a control problem, requiring (a) feedback of the observed climate state to manage significant uncertainty in both the radiative forcing and the climate's dynamic response to this forcing, and (b) optimization of the distribution of radiative effect to minimize regional disparities as well as side-effects from the geoengineering implementation. We present recent progress on control for this challenging problem, building on [1, 2], and discuss open research gaps. This is the first time an explicit external feedback loop has been implemented in a fully coupled general circulation model of the Earth's climate.

Engineering and Applied Sciences

An oblivious subspace embedding (OSE) given some parameters \(\epsilon\), d is a distribution \(\mathcal{D}\) over matrices \(\Pi \in \mathbb{R}^{m×n}\) such that for any linear subspace \(W \subseteq \mathbb{R}^n\) with dim(W) = d, \(\mathbb{P}_{\Pi \sim \mathcal{D}}(\forall x \in W ||\Pi x||_2 \in (1 \pm \epsilon)||x||_2) > 2/3\). We show that a certain class of distributions, Oblivious Sparse Norm-Approximating Projections (OSNAPs), provides OSE's with \(m = O(d^{1+\gamma}/\epsilon^2)\), and where every matrix \(\Pi\) in the support of the OSE has only \(s = O_{\gamma}(1/\epsilon)\) non-zero entries per column, for \(\gamma > 0\) any desired constant. Plugging OSNAPs into known algorithms for approximate least squares regression, \(\ell_p\) regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: we show that for any fixed \(U \in \mathbb{R}^{n×d}\) with orthonormal columns and random sparse \(\Pi\), all singular values of \(\Pi U\) lie in \([1 - \epsilon, 1 + \epsilon]\) with good probability. This can be seen as a generalization of the sparse Johnson-Lindenstrauss lemma, which was concerned with d = 1. Our methods also recover a slightly sharper version of a main result of [Clarkson-Woodruff, STOC 2013], with a much simpler proof. That is, we show that OSNAPs give an OSE with \(m = O(d^2/\epsilon^2)\), \(s = 1\)., Engineering and Applied Sciences

We apply hierarchical sparse coding, a form of deep learning, to model user-driven workloads based on on-chip hardware performance counters. We then predict periods of low instruction throughput, during which frequency and voltage can be scaled to reclaim power. Using a multi-layer coding structure, our method progressively codes counter values in terms of a few prominent features learned from data, and passes them to a Support Vector Machine (SVM) classifier where they act as signatures for predicting future workload states. We show that prediction accuracy and look-ahead range improve significantly over linear regression modeling, giving more time to adjust power management settings. Our method relies on learning and feature extraction algorithms that can discover and exploit hidden statistical invariances specific to workloads. We argue that, in addition to achieving superior prediction performance, our method is fast enough for practical use. To our knowledge, we are the first to use deep learning at the instruction level for workload prediction and on-chip power adaptation., Engineering and Applied Sciences