Background

Today, scientists, engineers, educators, citizens, and decision-makers have unprecedented amounts and types of data available to them. Data come from many disparate sources, including scientific instruments, medical devices, telescopes, microscopes, satellites; digital media including text, video, audio, e-mail, weblogs, twitter feeds, image collections, click streams, and financial transactions; dynamic sensor, social, and other types of networks; scientific simulations, models, and surveys; or computational analysis of observational data. Data can be temporal, spatial, or dynamic; structured or unstructured. Information and knowledge derived from data can differ in representation, complexity, granularity, context, provenance, reliability, trustworthiness, and scope. Data can also differ in the rate at which they are generated and accessed. The phrase “big data” refers to the kinds of data that challenge existing analytical methods due to size, complexity, or rate of availability.

The challenges in managing and analyzing “big data” can require fundamentally new techniques and technologies in order to handle the size, complexity, or rate of availability of these data. At the same time, the advent of big data offers unprecedented opportunities for data-driven discovery and decision-making in virtually every area of human endeavor. A key example of this is the scientific discovery process, which is a cycle involving data analysis, hypothesis generation, the design and execution of new experiments, hypothesis testing, and theory refinement. Realizing the transformative potential of big data requires addressing many challenges in the management of data and knowledge, computational methods for data analysis, and automating many aspects of data-enabled discovery processes. Combinations of computational, mathematical, and statistical techniques, methodologies, and theories are needed to enable these advances.

On March 29, 2012, the White House announced the Big Data Research and Development Initiative to mobilize the research and development toward Big Data analytics for solving many of the nation's most pressing challenges. A great many agencies are involved, spanning from National Science Foundation (NSF) and National Institutes of Health to the Department of Defense and the Department of Energy. Signal processing and systems engineering communities can be important contributors to big data research and development, complementing computer and information science-based efforts in this direction. Big data analytics entail high-dimensional, decentralized, online, and robust statistical signal processing, as well as large, distributed, fault-tolerant, and intelligent systems engineering. There is a need and opportunity for the signals and systems communities to jointly pursue big data research and development.

Despite the relatively short history of compressive sensing (CS) theory pioneered by the work by Candès, Romberg, and Tao [393, 394, 395] and Donoho [396], the numbers of studies and publications in this area have become amazingly large. On the other hand, the applications of CS just begin to appear. The inborn nature that many signals can be represented by sparse vectors has been recognized in many areas of applications. Examples in wireless communication include the sparse channel impulse response in the time domain, the sparse unitization of the spectrum, and the time and spatial sparsity in the wireless sensor networks. For each of these sparse signals, there are innovative signal acquisition schemes that not only satisfy the requirements by the CS theory, but also are easily realizable on hardware. Efficient signal-recovery algorithms for each system are also available. They guarantee stable signal recovery with high probability.

In this chapter, we provide a concise overview of CS basics and some of its extensions. In subsequent chapters, we focus on CS algorithms and specific areas of CS research related to bid data. This chapter begins with Section 8.1, which gives the motivation of CS, illustrates the typical steps of CS by an example, summarizes the key components CS, and discusses how nearly sparse signals and measurement noise are treated in robust CS. Following these discussions, Section 8.2 compares CS with traditional sensing and examines their advantages and disadvantages. The foundation of CS, sparse representation, is studied in Section 8.3, which briefly covers sparsifying transforms, analytic dictionaries, learned dictionaries, as well as a few extensions of sparse modeling. Next, Section 8.4 discusses a variety of conditions under which one can trust CS for encoding signals during sensing and recovering them faithfully after sensing. Then, two synthetic examples are given to close this chapter. Finally, we outline some applications for CS in Section 8.5.

Background

The Nyquist/Shannon sampling theory has been accepted as the doctrine for signal acquisition and processing ever since it was implied by the work of Nyquist in 1928 [397] and proved by Shannon in 1949 [398]. The theorem says that to exactly reconstruct an arbitrary band-limited signal from its samples, the sampling rate needs to be at least twice the bandwidth.

Introduction

The development of smart grid, impelled by the increasing demand from industrial and residential customers together with the aging power infrastructure, has become an urgent global priority due to its potential economic, environmental, and societal benefits. Smart grid refers to the next-generation electric power system which aims to provide reliable, efficient, secure, and quality energy generation/distribution/consumption using modern information, communications, and electronics technology. A distributed and user-centric system will be introduced in smart grid, which will incorporate end consumers into its decision processes to provide a cost-effective and reliable energy supply. In smart grid, the modern communication infrastructure [599] will play a vital role in managing, controlling, and optimizing different devices and systems. Information and communication technologies will offer the power grid with the capability of supporting two-way energy and information flow, quick isolating and restoring power outages, facilitating the integration of renewable energy sources into the grid, and empowering the consumer with tools for optimizing their energy consumption.

The inevitable coupling between information/communication technologies and physical operations is expected to present unique challenges as well as opportunities for smart grid. On the one hand, we are observing increasing integration between cyber operations and physical infrastructures for generation, transmission, and distribution control in the electric power grid. Yet the security and reliability of the power grid are not guaranteed at all times and some failures can cause significant problems for the producers and consumers of electricity. For example, the 2003 Northeast power blackout [600] showed that even a small failure in a part of the grid has cascading effects causing billions of dollars in economic losses. Nowadays, the consolidation of physical and cyber components gives rise to security threats in the power grid, which can result in power outages and even system blackouts [601], or substantial economical loss due to its non-optimal operation.

On the other hand, the anticipated smart grid data deluge, generated by the sensing and measurement devices and reinforced by communication and information technologies, provides us with the potential to enhance the security and reliability of smart grid. This “big data,” if effectively managed and translated into actionable insights, has the potential to increase revenue and operational efficiency, improve energy conservation, streamline the utilization of sustainable energy sources, and ensure grid resiliency.

Introduction

Wireless sensor networks provide a model in which sensors are deployed in large numbers where traditional wired or wireless networks are not available/appropriate. Their intended uses include terrain monitoring, surveillance, and discovery [644] with applications to geological tasks such as tsunami and earthquake detection, military surveillance, search and rescue operations, building safety surveillance (e.g., for fire detection), and biological systems.

The major difference between sensor networks and traditional networks is that unlike a host computer or a router, a sensor is typically a tightly constrained device. Sensors not only lack long life spans due to their limited battery power, but also possess little computational power and memory storage [645]. As a result of the limited capabilities of individual sensors, one sensor usually can only collect a small amount of data from its environment and carry out a small number of computations. Therefore, a single sensor is generally expected to work in cooperation with other sensors in the network. As a result of this unique structure, a sensor network is typically data-centric and query-based [646]. When a query is made, the network is expected to distribute the query, gather values from individual sensors, and compute a final value. This final value typically represents key properties of the area where the network is deployed; examples of such values are MAXIMUM, MINIMUM, QUANTILE, AVERAGE, and SUM [647, 648] over the individual parameters of the sensors, such as temperature, air or water composition, and so on. As an example, consider a sensor network monitoring the average vibration level around a volcano. Each sensor lying in the crater area submits its own value representing the level of activity in a small area around it. Then the data values are relayed through the network; in this process, they are aggregated so that fewer messages need to be sent. Ultimately, the base station obtains the aggregated information about the area being monitored.

In addition to their distributed nature, most sensor networks are highly redundant to compensate for the low reliability of the sensors and environmental conditions. Since the data from a sensor network is the aggregation of data from individual sensors, the number of sensors in a network has a direct influence on the delay incurred in answering a query.

Introduction

Sublinear algorithms were initially developed in the theoretical computer science community. The sublinear algorithm can be seen as one further classification of the approximation algorithm. It studies the classic trade-off between algorithm processing time and algorithm output quality.

In a conventional approximation algorithm, the algorithm can output an approximate result that deviates from the optimal result (the deviation is bounded), so that the algorithm processing time can become faster. One hidden implication of the approximation algorithm is that the approximate result is 100% guaranteed within the bound. In a sublinear algorithm, such an implication is relaxed. More specifically, a sublinear algorithm outputs an approximate result that deviates from the optimal result (the deviation is bounded) for a (usually) majority of the time. As a concrete example, a sublinear algorithm usually says that the output of the algorithm differs from the optimal solution by at most 0.1 (the bound) at least 95% of the time (the confidence).

From the theoretical research point of view, sublinear algorithms become a new category of approximation algorithms. From the practical point of view, sublinear algorithms provide two controlling parameters for the user in making trade-offs, while approximation algorithms have only one controlling parameter.

Sublinear algorithms are developed based on random and probabilistic techniques. Note, however, that the guarantee of a sublinear algorithm is on the individual outputs of this algorithm. In this sense, the sublinear algorithm differs from stochastic techniques, which analyze the mean and variance of a system in a steady state. For example, a typical queuing theory result is that the expected waiting time is 100 seconds.

In the theoretical computer sciences in the past few years, there have been many studies on sublinear algorithms. Sublinear algorithms have been developed for many classic computer science problems, such as finding the frequently element, finding distinct elements, and others; and for graph problems, such as finding the minimum spanning tree, and others; and for geometry problems, such as finding the intersection of two polygons, and others. Sublinear algorithms can be broadly classified into sublinear time algorithms, sublinear space algorithms, and sublinear communication algorithms, where the amount of time, storage space, or communications needed is o(N) with N as the input size.

Nowadays, modern communication networks play an important role such as in electric power systems, mobile cloud computing, smart city evolution, and personal healthcare. The employed novel telecommunication technologies make data collection much easier for system operation and control, enable more efficient data transmission for mobile applications, and promise a more intelligent sensing and monitoring for metropolitan city regions. Meanwhile, we are witnessing an unprecedented rise in volume, variety and velocity of information in modern communication networks. A large volume of data are generated by our digital equipments such as mobile devices and computers, smart meters and household appliances, as well as surveillance cameras and sensorequipped mass rapid transit around the city. The information exposition of big data in modern communication networks makes statistical and computational methods significantly important for data analysis, processing, and optimization. The network operators or service providers who can develop and exploit efficient methods to tackle big data challenges will ensure network security and resiliency, gain market share, increase revenue with distinctive quality of service, as well as achieve intelligent network operation and management.

The unprecedented “big data,” reinforced by communication and information technologies, presents us opportunities and challenges. On the one hand, the inferential power of algorithms, which have been shown to be successful on modest-sized data sets, may be amplified by the massive data set. Those data analytic methods for the unprecedented volumes of data promises to improve personalized business model design, intelligent social network analysis, smart city development, efficient healthcare and medical data management, and the smart grid evolution. On the other hand, the sheer volume of data makes it unpractical to collect, store, and process the data set in a centralized fashion. Moreover, the massive data sets are noisy, incomplete, heterogeneous, structured, prone to outliers, and vulnerable to cyber attacks. The error rates, which are part and parcel of any inferential algorithm, may also be amplified by the massive data. Finally, the “big data” problems often come with time constraints, where a mediumquality answer that is obtained quickly can be more useful than a high-quality answer that is obtained slowly. Overall, we are facing a problem in which the classic resources of computation, such as time, space, and energy, are intertwined in complex ways with the massive data resources.

Introduction

While the performance of a data parallelism structure is primarily determined by the amount of data that need to be processed, since data are processed by different machines in parallel, the completion time of an application job is determined by the last finished machine. It is a grand challenge to distribute data load evenly to different machines. In the default configuration ofMapReduce Hadoop, this is done by developing a hash function in the shuffling phase so that the intermediate results outputted by the mapper phase will be distributed evenly to different machines in the reduce phase. Such default configuration emphasizes the “common” case. Clearly, it is not optimal for various scenarios, and in many situations such configuration performs poorly.

There are many research studies on this grand problem. There are the reactive approach and the proactive approach. In the reactive approach, the workloads of different machines are monitored and workloads can be migrated from one machine to another in case there is a large skew of the workloads. SkewTune is one good example representing reactive approach [22]. In the proactive approach, systems try to understand the possible workloads the data to be processed can generate on each machine, so that when the data are dispatched to different machines in a load aware manner.

In this chapter, we study a proactive approach to improve performance of processing large data in MapReduce using sublinear algorithms.

The Data Skew Problem of MapReduce Jobs

When running MapReduce jobs, most of the studies have assumed that the input data are of uniform distribution, which, often being hashed to reduce worker nodes, naturally leads to a desirable balanced load in the later stages. The real-world data, however, are not necessarily uniform, and often exhibit a remarkable degree of skewness. For example, in PageRank, the graph commonly includes nodes with much higher degrees of incoming edges than others [21], and in Inverted Index, certain content can appear in many more documents than others [22]. Such a skewed distribution of the input or intermediate data can result in a small number of mappers or reducers taking a significantly longer time to complete than others [19]. Recent experimental studies [21, 19, 22] have shown that, in the CloudBurst application with a biology data set of a bimodal distribution [635], the slowest map task takes five times as long to complete as the fastest.

Deep learning (also known as deep structured learning, hierarchical learning, or deep machine learning) is a branch of machine learning based on a set of algorithms that attempt to model high-level abstractions in data by using a deep graph with multiple processing layers, composed of multiple linear and nonlinear transformations. Deep learning has been characterized as a class of machine learning algorithms with the following characteristics [257]:

1. • They use a cascade of many layers of nonlinear processing units for feature extraction and transformation. Each successive layer uses the output from the previous layer as input. The algorithms may be supervised or unsupervised and applications include pattern analysis (unsupervised) and classification (supervised).

2. • They are based on the (unsupervised) learning of multiple levels of features or representations of the data. Higher-level features are derived from lower-level features to form a hierarchical representation.

3. • They are part of the broader machine learning field of learning representations of data.

4. • They learn multiple levels of representations that correspond to different levels of abstraction; the levels form a hierarchy of concepts.

These definitions have in common: multiple layers of nonlinear processing units and the supervised or unsupervised learning of feature representations in each layer, with the layers forming a hierarchy from low-level to high-level features. Various deep learning architectures such as deep neural networks, convolutional deep neural networks, deep belief networks (DBN), and recurrent neural networks have been applied to fields like computer vision, automatic speech recognition, natural language processing, audio recognition, and bioinformatics where they have been shown to produce state-of-the-art results on various tasks.

In this chapter we start in Section 7.1 with an introduction, giving a brief history of this field, the relevant literature, and its applications. Then we study some basic concepts of deep learning such as convolutional neural networks, recurrent neural networks, backpropagation algorithm, restricted Boltzmann machines, and deep learning networks in Section 7.2. Then we illustrate three examples for Apache Spark implementation for mobile big data (MBD), user moving pattern extraction, and combination with nonparametric Bayesian learning, respectively, in Sections 7.3 through 7.5. Finally, we have summary in Section 7.6.

In this chapter, we discuss distributed algorithms for solving large-scale optimization problems over networks. In particular, the optimization problem is defined over a network of nodes/agents where each of them may have a piece of data, or may be in charge of updating a subset of variables, and they are required to collaboratively perform the desired optimization. The key question to be addressed is, under various problem settings, what protocols should the agents follow so as to efficiently optimize the overall problem. These types of distributed optimizing algorithms have recently become increasingly important in various big data problems, with applications ranging from distributed machine learning, signal processing, networking, multi-agent systems, parallel optimization, etc. There are a few driving forces behind these new trends, as we briefly list below:

1. 1. The advances in sensor technologies makes distributed data acquisition ubiquitous.

2. 2. The increasing size of optimization problems in big data era calls for distributed data storage.

3. 3. Privacy issues in big data problem prevents direct data exchange among different (possibly geographically distributed) data sources.

4. 4. Using multi-core high-performance computing systems (with either shared or distributed memory) to solve big data optimization problems can significantly reduce the solution time.

In this chapter, we present a few recent algorithms for solving such distributed optimization problems. We will cover a wide range of algorithms and discuss their convergence behavior, as well as their performance in terms of scaling with network/problem sizes.

The chapter is organized as follows. In Sections 9.1–9.4, we present a general problem formulation and a few popular first-order methods. In Section 9.5, we discuss a special cases of the general formulation (i.e., the global consensus problem). In Section 9.6, we compare various algorithms presented in this chapter.

Background

Problem Formulation

The Optimization Problem

Consider a network with N distributed agents, each capable of communicating with its immediate neighbors; see Figure 9.1 for an illustration.