OpenRaiser/Intern-Atlas huggingface dataset:
Crowdsourced Live Streaming over the Cloud
Venue: arXiv cs.MM 2015
Year: 2015

Empowered by today's rich tools for media generation and distribution, and the convenient Internet access, crowdsourced streaming generalizes the single-source streaming paradigm by including massive contributors for a video channel. It calls a joint optimization along the path from crowdsourcers, through streaming servers, to the end-users to minimize the overall latency. The dynamics of the video sources, together with the globalized request demands and the high computation demand from each sourcer, make crowdsourced live streaming challenging even with powerful support from modern cloud computing. In this paper, we present a generic framework that facilitates a cost-effective cloud service for crowdsourced live streaming. Through adaptively leasing, the cloud servers can be provisioned in a fine granularity to accommodate geo-distributed video crowdsourcers. We present an optimal solution to deal with service migration among cloud instances of diverse lease prices. It also addresses the location impact to the streaming quality. To understand the performance of the proposed strategies in the realworld, we have built a prototype system running over the planetlab and the Amazon/Microsoft Cloud. Our extensive experiments demonstrate that the effectiveness of our solution in terms of deployment cost and streaming quality.
On the Susceptibility of the Deferred Acceptance Algorithm
Venue: arXiv cs.GT 2015
Year: 2015

The Deferred Acceptance Algorithm (DAA) is the most widely accepted and used algorithm to match students, workers, or residents to colleges, firms or hospitals respectively. In this paper, we consider for the first time, the complexity of manipulating DAA by agents such as colleges that have capacity more than one. For such agents, truncation is not an exhaustive strategy. We present efficient algorithms to compute a manipulation for the colleges when the colleges are proposing or being proposed to. We then conduct detailed experiments on the frequency of manipulable instances in order to get better insight into strategic aspects of two-sided matching markets. Our results bear somewhat negative news: assuming that agents have information other agents' preference, they not only often have an incentive to misreport but there exist efficient algorithms to find such a misreport.
Incentive Design and Market Evolution of Mobile User-Provided Networks
Venue: arXiv cs.GT 2015
Year: 2015

An operator-assisted user-provided network (UPN) has the potential to achieve a low cost ubiquitous Internet connectivity, without significantly increasing the network infrastructure investment. In this paper, we consider such a network where the network operator encourages some of her subscribers to operate as mobile Wi-Fi hotspots (hosts), providing Internet connectivity for other subscribers (clients). We formulate the interaction between the operator and mobile users as a two-stage game. In Stage I, the operator determines the usage-based pricing and quota-based incentive mechanism for the data usage. In Stage II, the mobile users make their decisions about whether to be a host, or a client, or not a subscriber at all. We characterize how the users' membership choices will affect each other's payoffs in Stage II, and how the operator optimizes her decision in Stage I to maximize her profit. Our theoretical and numerical results show that the operator's maximum profit increases with the user density under the proposed hybrid pricing mechanism, and the profit gain can be up to 50\% in a dense network comparing with a pricing-only approach with no incentives.
First-order regret bounds for combinatorial semi-bandits
Venue: arXiv cs.LG 2015
Year: 2015

We consider the problem of online combinatorial optimization under semi-bandit feedback, where a learner has to repeatedly pick actions from a combinatorial decision set in order to minimize the total losses associated with its decisions. After making each decision, the learner observes the losses associated with its action, but not other losses. For this problem, there are several learning algorithms that guarantee that the learner's expected regret grows as $\widetilde{O}(\sqrt{T})$ with the number of rounds $T$. In this paper, we propose an algorithm that improves this scaling to $\widetilde{O}(\sqrt{L_T^*})$, where $L_T^*$ is the total loss of the best action. Our algorithm is among the first to achieve such guarantees in a partial-feedback scheme, and the first one to do so in a combinatorial setting.
Neighbor Cell List Optimization for Femtocell-to-Femtocell Handover in Dense Femtocellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

Dense femtocells are the ultimate goal of the femtocellular network deployment. Among three types of handovers: femtocell-to-macrocell, macrocell-to-femtocell, and femtocell-to-femtocell, the latter two are the main concern for the dense femtocellular network deployment. For these handover cases, minimum as well appropriate neighbor cell list is the key element for the successful handover. In this paper, we propose an algorithm to make minimum but appropriate number of neighbor femtocell list for the femtocell-to-femtocell handover. Our algorithm considers received signal level from femto APs (FAPs); open and close access cases; and detected frequencyfrom the neighbor femtocells. The simulation results show that the proposed scheme is able to attain minimum but optimal number of neighbor femtocell list for the possible femtocell-to-femtocell handover.
Upper Bound on the Capacity of the Nonlinear Schrödinger Channel
Venue: arXiv cs.IT 2015
Year: 2015

It is shown that the capacity of the channel modeled by (a discretized version of) the stochastic nonlinear Schrödinger (NLS) equation is upper-bounded by $\log(1+\text{SNR})$ with $\text{SNR}=\mathcal P_0/σ^2(z)$, where $\mathcal P_0$ is the average input signal power and $σ^2(z)$ is the total noise power up to distance $z$. The result is a consequence of the fact that the deterministic NLS equation is a Hamiltonian energy-preserving dynamical system.
Visualizing BACnet data to facilitate humans in building-security decision-making
Venue: arXiv cs.CR 2015
Year: 2015

Building automation systems (BAS) are interlinked networks of hardware and software, which monitor and control events in the buildings. One of the data communication protocols used in BAS is Building Automation and Control networking protocol (BACnet) which is an internationally adopted ISO standard for the communication between BAS devices. Although BAS focus on providing safety for inhabitants, decreasing the energy consumption of buildings and reducing their operational cost, their security suffers due to the inherent complexity of the modern day systems. The issues such as monitoring of BAS effectively present a significant challenge, i.e., BAS operators generally possess only partial situation awareness. Especially in large and inter-connected buildings, the operators face the challenge of spotting meaningful incidents within large amounts of simultaneously occurring events, causing the anomalies in the BAS network to go unobserved. In this paper, we present the techniques to analyze and visualize the data for several events from BAS devices in a way that determines the potential importance of such unusual events and helps with the building-security decision making. We implemented these techniques as a mobile (Android) based application for displaying application data and as tools to analyze the communication flows using directed graphs.
Approximate Message Passing with Restricted Boltzmann Machine Priors
Venue: arXiv cs.IT 2015
Year: 2015

Approximate Message Passing (AMP) has been shown to be an excellent statistical approach to signal inference and compressed sensing problem. The AMP framework provides modularity in the choice of signal prior; here we propose a hierarchical form of the Gauss-Bernouilli prior which utilizes a Restricted Boltzmann Machine (RBM) trained on the signal support to push reconstruction performance beyond that of simple iid priors for signals whose support can be well represented by a trained binary RBM. We present and analyze two methods of RBM factorization and demonstrate how these affect signal reconstruction performance within our proposed algorithm. Finally, using the MNIST handwritten digit dataset, we show experimentally that using an RBM allows AMP to approach oracle-support performance.
Optimal Sparse Linear Auto-Encoders and Sparse PCA
Venue: arXiv cs.LG 2015
Year: 2015

Principal components analysis (PCA) is the optimal linear auto-encoder of data, and it is often used to construct features. Enforcing sparsity on the principal components can promote better generalization, while improving the interpretability of the features. We study the problem of constructing optimal sparse linear auto-encoders. Two natural questions in such a setting are: i) Given a level of sparsity, what is the best approximation to PCA that can be achieved? ii) Are there low-order polynomial-time algorithms which can asymptotically achieve this optimal tradeoff between the sparsity and the approximation quality? In this work, we answer both questions by giving efficient low-order polynomial-time algorithms for constructing asymptotically \emph{optimal} linear auto-encoders (in particular, sparse features with near-PCA reconstruction error) and demonstrate the performance of our algorithms on real data.
Variable-Length Feedback Codes under a Strict Delay Constraint
Venue: arXiv cs.IT 2015
Year: 2015

We study variable-length feedback (VLF) codes under a strict delay constraint to maximize their average transmission rate (ATR) in a discrete memoryless channel (DMC) while considering periodic decoding attempts. We first derive a lower bound on the maximum achievable ATR, and confirm that the VLF code can outperform non-feedback codes with a larger delay constraint. We show that for a given decoding period, as the strict delay constraint, L, increases, the gap between the ATR of the VLF code and the DMC capacity scales at most on the order of O(L^{-1}) instead of O(L^{-1/2}) for non-feedback codes as shown in Polyanskiy et al. ["Channel coding rate in the finite blocklengh regime," IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2307-2359, May 2010.]. We also develop an approximation indicating that, for a given L, the achievable ATR increases as the decoding period decreases.
A deterministic sublinear-time nonadaptive algorithm for metric $1$-median selection
Venue: arXiv cs.DS 2015
Year: 2015

We give a deterministic $O(hn^{1+1/h})$-time $(2h)$-approximation nonadaptive algorithm for $1$-median selection in $n$-point metric spaces, where $h\in\mathbb{Z}^+\setminus\{1\}$ is arbitrary. Our proof generalizes that of Chang.
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions
Venue: arXiv cs.LG 2015
Year: 2015

We show that kernel-based quadrature rules for computing integrals can be seen as a special case of random feature expansions for positive definite kernels, for a particular decomposition that always exists for such kernels. We provide a theoretical analysis of the number of required samples for a given approximation error, leading to both upper and lower bounds that are based solely on the eigenvalues of the associated integral operator and match up to logarithmic terms. In particular, we show that the upper bound may be obtained from independent and identically distributed samples from a specific non-uniform distribution, while the lower bound if valid for any set of points. Applying our results to kernel-based quadrature, while our results are fairly general, we recover known upper and lower bounds for the special cases of Sobolev spaces. Moreover, our results extend to the more general problem of full function approximations (beyond simply computing an integral), with results in L2- and L$\infty$-norm that match known results for special cases. Applying our results to random features, we show an improvement of the number of random features needed to preserve the generalization guarantees for learning with Lipschitz-continuous losses.
Towards a Tractable Analysis of Localization Fundamentals in Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

When dedicated positioning systems, such as GPS, are unavailable, a mobile device has no choice but to fall back on its cellular network for localization. Due to random variations in the channel conditions to its surrounding base stations (BS), the mobile device is likely to face a mix of both favorable and unfavorable geometries for localization. Analytical studies of localization performance (e.g., using the Cramér-Rao lower bound) usually require that one fix the BS geometry, and favorable geometries have always been the preferred choice in the literature. However, not only are the resulting analytical results constrained to the selected geometry, this practice is likely to lead to overly-optimistic expectations of typical localization performance. Ideally, localization performance should be studied across all possible geometric setups, thereby also removing any selection bias. This, however, is known to be hard and has been carried out only in simulation. In this paper, we develop a new tractable approach where we endow the BS locations with a distribution by modeling them as a Poisson point process (PPP), and use tools from stochastic geometry to obtain easy-to-use expressions for key performance metrics. In particular, we focus on the probability of detecting some minimum number of BSs, which is shown to be closely coupled with a network operator's ability to obtain satisfactory localization performance (e.g., meet FCC E911 requirements). This metric is indifferent to the localization technique (e.g., TOA, TDOA, AOA, or hybrids thereof), though different techniques will presumably lead to different BS hearability requirements. In order to mitigate excessive interference due to the presence of dominant interferers in the form of other BSs, we incorporate both BS coordination and frequency reuse in the proposed framework and quantify the resulting performance gains analytically.
Topology Detection in Microgrids with Micro-Synchrophasors
Venue: arXiv cs.SY 2015
Year: 2015

Network topology in distribution networks is often unknown, because most switches are not equipped with measurement devices and communication links. However, knowledge about the actual topology is critical for safe and reliable grid operation. This paper proposes a voting-based topology detection method based on micro-synchrophasor measurements. The minimal difference between measured and calculated voltage angle or voltage magnitude, respectively, indicates the actual topology. Micro-synchrophasors or micro-Phasor Measurement Units (μPMU) are high-precision devices that can measure voltage angle differences on the order of ten millidegrees. This accuracy is important for distribution networks due to the smaller angle differences as compared to transmission networks. For this paper, a microgrid test bed is implemented in MATLAB with simulated measurements from μPMUs as well as SCADA measurement devices. The results show that topologies can be detected with high accuracy. Additionally, topology detection by voltage angle shows better results than detection by voltage magnitude.
To Harvest and Jam: A Paradigm of Self-Sustaining Friendly Jammers for Secure AF Relaying
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the use of multi-antenna harvest-and-jam (HJ) helpers in a multi-antenna amplify-and-forward (AF) relay wiretap channel assuming that the direct link between the source and destination is broken. Our objective is to maximize the secrecy rate at the destination subject to the transmit power constraints of the AF relay and the HJ helpers. In the case of perfect channel state information (CSI), the joint optimization of the artificial noise (AN) covariance matrix for cooperative jamming and the AF beamforming matrix is studied using semi-definite relaxation (SDR) which is tight, while suboptimal solutions are also devised with lower complexity. For the imperfect CSI case, we provide the equivalent reformulation of the worst-case robust optimization to maximize the minimum achievable secrecy rate. Inspired by the optimal solution to the case of perfect CSI, a suboptimal robust scheme is proposed striking a good tradeoff between complexity and performance. Finally, numerical results for various settings are provided to evaluate the proposed schemes.
The VC-Dimension of Similarity Hypotheses Spaces
Venue: arXiv cs.LG 2015
Year: 2015

Given a set $X$ and a function $h:X\longrightarrow\{0,1\}$ which labels each element of $X$ with either $0$ or $1$, we may define a function $h^{(s)}$ to measure the similarity of pairs of points in $X$ according to $h$. Specifically, for $h\in \{0,1\}^X$ we define $h^{(s)}\in \{0,1\}^{X\times X}$ by $h^{(s)}(w,x):= \mathbb{1}[h(w) = h(x)]$. This idea can be extended to a set of functions, or hypothesis space $\mathcal{H} \subseteq \{0,1\}^X$ by defining a similarity hypothesis space $\mathcal{H}^{(s)}:=\{h^{(s)}:h\in\mathcal{H}\}$. We show that ${vc-dimension}(\mathcal{H}^{(s)}) \in Θ({vc-dimension}(\mathcal{H}))$.
Autonomous Vehicle Public Transportation System: Scheduling and Admission Control
Venue: arXiv cs.SY 2015
Year: 2015

Technology of autonomous vehicles (AVs) is getting mature and many AVs will appear on the roads in the near future. AVs become connected with the support of various vehicular communication technologies and they possess high degree of control to respond to instantaneous situations cooperatively with high efficiency and flexibility. In this paper, we propose a new public transportation system based on AVs. It manages a fleet of AVs to accommodate transportation requests, offering point-to-point services with ride sharing. We focus on the two major problems of the system: scheduling and admission control. The former is to configure the most economical schedules and routes for the AVs to satisfy the admissible requests while the latter is to determine the set of admissible requests among all requests to produce maximum profit. The scheduling problem is formulated as a mixed-integer linear program and the admission control problem is cast as a bilevel optimization, which embeds the scheduling problem as the major constraint. By utilizing the analytical properties of the problem, we develop an effective genetic-algorithm-based method to tackle the admission control problem. We validate the performance of the algorithm with real-world transportation service data.
Spreading Processes over Socio-Technical Networks with Phase-Type Transmissions
Venue: arXiv cs.SI 2015
Year: 2015

Most theoretical tools available for the analysis of spreading processes over networks assume exponentially distributed transmission and recovery times. In practice, the empirical distribution of transmission times for many real spreading processes, such as the spread of web content through the Internet, are far from exponential. To bridge this gap between theory and practice, we propose a methodology to model and analyze spreading processes with arbitrary transmission times using phase-type distributions. Phase-type distributions are a family of distributions that is dense in the set of positive-valued distributions and can be used to approximate any given distributions. To illustrate our methodology, we focus on a popular model of spreading over networks: the susceptible-infected-susceptible (SIS) networked model. In the standard version of this model, individuals informed about a piece of information transmit this piece to its neighbors at an exponential rate. In this paper, we extend this model to the case of transmission rates following a phase-type distribution. Using this extended model, we analyze the dynamics of the spread based on a vectorial representations of phase-type distributions. We illustrate our results by analyzing spreading processes over networks with transmission and recovery rates following a Weibull distribution.
Interdependent Security with Strategic Agents and Cascades of Infection
Venue: arXiv cs.SI 2015
Year: 2015

We investigate cascades in networks consisting of strategic agents with interdependent security. We assume that the strategic agents have choices between i) investing in protecting themselves, ii) purchasing insurance to transfer (some) risks, and iii) taking no actions. Using a population game model, we study how various system parameters, such as node degrees, infection propagation rate, and the probability with which infected nodes transmit infection to neighbors, affect nodes' choices at Nash equilibria and the resultant price of anarchy/stability. In addition, we examine how the probability that a single infected node can spread the infection to a significant portion of the entire network, called cascade probability, behaves with respect to system parameters. In particular, we demonstrate that, at least for some parameter regimes, the cascade probability increases with the average degree of nodes.
A Dictionary Approach to EBSD Indexing
Venue: arXiv cs.CV 2015
Year: 2015

We propose a framework for indexing of grain and sub-grain structures in electron backscatter diffraction (EBSD) images of polycrystalline materials. The framework is based on a previously introduced physics-based forward model by Callahan and De Graef (2013) relating measured patterns to grain orientations (Euler angle). The forward model is tuned to the microscope and the sample symmetry group. We discretize the domain of the forward model onto a dense grid of Euler angles and for each measured pattern we identify the most similar patterns in the dictionary. These patterns are used to identify boundaries, detect anomalies, and index crystal orientations. The statistical distribution of these closest matches is used in an unsupervised binary decision tree (DT) classifier to identify grain boundaries and anomalous regions. The DT classifies a pattern as an anomaly if it has an abnormally low similarity to any pattern in the dictionary. It classifies a pixel as being near a grain boundary if the highly ranked patterns in the dictionary differ significantly over the pixels 3x3 neighborhood. Indexing is accomplished by computing the mean orientation of the closest dictionary matches to each pattern. The mean orientation is estimated using a maximum likelihood approach that models the orientation distribution as a mixture of Von Mises-Fisher distributions over the quaternionic 3-sphere. The proposed dictionary matching approach permits segmentation, anomaly detection, and indexing to be performed in a unified manner with the additional benefit of uncertainty quantification. We demonstrate the proposed dictionary-based approach on a Ni-base IN100 alloy.
A Comparative Study of Scheduling Techniques for Multimedia Applications on SIMD Pipelines
Venue: arXiv cs.DC 2015
Year: 2015

Parallel architectures are essential in order to take advantage of the parallelism inherent in streaming applications. One particular branch of these employ hardware SIMD pipelines. In this paper, we analyse several scheduling techniques, namely ad hoc overlapped execution, modulo scheduling and modulo scheduling with unrolling, all of which aim to efficiently utilize the special architecture design. Our investigation focuses on improving throughput while analysing other metrics that are important for streaming applications, such as register pressure, buffer sizes and code size. Through experiments conducted on several media benchmarks, we present and discuss trade-offs involved when selecting any one of these scheduling techniques.