OpenRaiser/Intern-Atlas huggingface dataset:
An extension of the Georgiou-Smith example: Boundedness and attractivity in the presence of unmodelled dynamics via nonlinear PI control
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, a nonlinear extension of the Georgiou-Smith system is considered and robustness results are proved for a class of nonlinear PI controllers with respect to fast parasitic first-order dynamics. More specifically, for a perturbed nonlinear system with sector bounded nonlinearity and unknown control direction, sufficient conditions for global boundedness and attractivity have been derived. It is shown that the closed loop system is globally bounded and attractive if (i) the unmodelled dynamics are sufficiently fast and (ii) the PI control gain has the Nussbaum function property. For the case of nominally unstable systems, the Nussbaum property of the control gain appears to be crucial. A simulation study confirms the theoretical results.
Parallel Wavelet Tree Construction
Venue: arXiv cs.DS 2015
Year: 2015

We present parallel algorithms for wavelet tree construction with polylogarithmic depth, improving upon the linear depth of the recent parallel algorithms by Fuentes-Sepulveda et al. We experimentally show on a 40-core machine with two-way hyper-threading that we outperform the existing parallel algorithms by 1.3--5.6x and achieve up to 27x speedup over the sequential algorithm on a variety of real-world and artificial inputs. Our algorithms show good scalability with increasing thread count, input size and alphabet size. We also discuss extensions to variants of the standard wavelet tree.
Improved Efficiency Guarantees in Auctions with Budgets
Venue: arXiv cs.GT 2015
Year: 2015

We study the efficiency guarantees in the simple auction environment where the auctioneer has one unit of divisible good to be distributed among a number of budget constrained agents. With budget constraints, the social welfare cannot be approximated by a better factor than the number of agents by any truthful mechanism. Thus, we follow a recent work by Dobzinski and Leme (ICALP 2014) to approximate the liquid welfare, which is the welfare of the agents each capped by her/his own budget. We design a new truthful auction with an approximation ratio of $\frac{\sqrt{5}+1}{2} \approx 1.618$, improving the best previous ratio of $2$ when the budgets for agents are public knowledge and their valuation is linear (additive). In private budget setting, we propose the first constant approximation auction with approximation ratio of $34$. Moreover, this auction works for any valuation function. Previously, only $O(\log n)$ approximation was known for linear and decreasing marginal (concave) valuations, and $O(\log^2 n)$ approximation was known for sub-additive valuations.
Downlink Cellular Network Analysis with Multi-slope Path Loss Models
Venue: arXiv cs.IT 2015
Year: 2015

Existing cellular network analyses, and even simulations, typically use the standard path loss model where received power decays like $\|x\|^{-α}$ over a distance $\|x\|$. This standard path loss model is quite idealized, and in most scenarios the path loss exponent $α$ is itself a function of $\|x\|$, typically an increasing one. Enforcing a single path loss exponent can lead to orders of magnitude differences in average received and interference powers versus the true values. In this paper we study \emph{multi-slope} path loss models, where different distance ranges are subject to different path loss exponents. We focus on the dual-slope path loss function, which is a piece-wise power law and continuous and accurately approximates many practical scenarios. We derive the distributions of SIR, SNR, and finally SINR before finding the potential throughput scaling, which provides insight on the observed cell-splitting rate gain. The exact mathematical results show that the SIR monotonically decreases with network density, while the converse is true for SNR, and thus the network coverage probability in terms of SINR is maximized at some finite density. With ultra-densification (network density goes to infinity), there exists a \emph{phase transition} in the near-field path loss exponent $α_0$: if $α_0 >1$ unbounded potential throughput can be achieved asymptotically; if $α_0 <1$, ultra-densification leads in the extreme case to zero throughput.
Measuring and Optimizing Cultural Markets
Venue: arXiv cs.SI 2015
Year: 2015

Social influence has been shown to create significant unpredictability in cultural markets, providing one potential explanation why experts routinely fail at predicting commercial success of cultural products. To counteract the difficulty of making accurate predictions, "measure and react" strategies have been advocated but finding a concrete strategy that scales for very large markets has remained elusive so far. Here we propose a "measure and optimize" strategy based on an optimization policy that uses product quality, appeal, and social influence to maximize expected profits in the market at each decision point. Our computational experiments show that our policy leverages social influence to produce significant performance benefits for the market, while our theoretical analysis proves that our policy outperforms in expectation any policy not displaying social information. Our results contrast with earlier work which focused on showing the unpredictability and inequalities created by social influence. Not only do we show for the first time that dynamically showing consumers positive social information under our policy increases the expected performance of the seller in cultural markets. We also show that, in reasonable settings, our policy does not introduce significant unpredictability and identifies "blockbusters". Overall, these results shed new light on the nature of social influence and how it can be leveraged for the benefits of the market.
Off-the-Grid Line Spectrum Denoising and Estimation with Multiple Measurement Vectors
Venue: arXiv cs.IT 2015
Year: 2015

Compressed Sensing suggests that the required number of samples for reconstructing a signal can be greatly reduced if it is sparse in a known discrete basis, yet many real-world signals are sparse in a continuous dictionary. One example is the spectrally-sparse signal, which is composed of a small number of spectral atoms with arbitrary frequencies on the unit interval. In this paper we study the problem of line spectrum denoising and estimation with an ensemble of spectrally-sparse signals composed of the same set of continuous-valued frequencies from their partial and noisy observations. Two approaches are developed based on atomic norm minimization and structured covariance estimation, both of which can be solved efficiently via semidefinite programming. The first approach aims to estimate and denoise the set of signals from their partial and noisy observations via atomic norm minimization, and recover the frequencies via examining the dual polynomial of the convex program. We characterize the optimality condition of the proposed algorithm and derive the expected convergence rate for denoising, demonstrating the benefit of including multiple measurement vectors. The second approach aims to recover the population covariance matrix from the partially observed sample covariance matrix by motivating its low-rank Toeplitz structure without recovering the signal ensemble. Performance guarantee is derived with a finite number of measurement vectors. The frequencies can be recovered via conventional spectrum estimation methods such as MUSIC from the estimated covariance matrix. Finally, numerical examples are provided to validate the favorable performance of the proposed algorithms, with comparisons against several existing approaches.
Distribution and Dependence of Extremes in Network Sampling Processes
Venue: arXiv cs.SI 2015
Year: 2015

We explore the dependence structure in the sampled sequence of large networks. We consider randomized algorithms to sample the nodes and study extremal properties in any associated stationary sequence of characteristics of interest like node degrees, number of followers or income of the nodes in Online Social Networks etc, which satisfy two mixing conditions. Several useful extremes of the sampled sequence like $k$th largest value, clusters of exceedances over a threshold, first hitting time of a large value etc are investigated. We abstract the dependence and the statistics of extremes into a single parameter that appears in Extreme Value Theory, called extremal index (EI). In this work, we derive this parameter analytically and also estimate it empirically. We propose the use of EI as a parameter to compare different sampling procedures. As a specific example, degree correlations between neighboring nodes are studied in detail with three prominent random walks as sampling techniques.
Multidimensional Digital Filters for Point-Target Detection in Cluttered Infrared Scenes
Venue: arXiv cs.CV 2015
Year: 2015

A 3-D spatiotemporal prediction-error filter (PEF), is used to enhance foreground/background contrast in (real and simulated) sensor image sequences. Relative velocity is utilized to extract point-targets that would otherwise be indistinguishable on spatial frequency alone. An optical-flow field is generated using local estimates of the 3-D autocorrelation function via the application of the fast Fourier transform (FFT) and inverse FFT. Velocity estimates are then used to tune in a background-whitening PEF that is matched to the motion and texture of the local background. Finite-impulse-response (FIR) filters are designed and implemented in the frequency domain. An analytical expression for the frequency response of velocity-tuned FIR filters, of odd or even dimension, with an arbitrary delay in each dimension, is derived.
On the Structure and the Number of Prime Implicants of 2-CNFs
Venue: arXiv cs.DM 2015
Year: 2015

Let $m(n, k)$ be the maximum number of prime implicants that any $k$-CNF on n variables can have. We show that $3^{n/3} \le m(n,2) \le (1+o(1))3^{n/3}$.
Isotropic Multiple Scattering Processes on Hyperspheres
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents several results about isotropic random walks and multiple scattering processes on hyperspheres ${\mathbb S}^{p-1}$. It allows one to derive the Fourier expansions on ${\mathbb S}^{p-1}$ of these processes. A result of unimodality for the multiconvolution of symmetrical probability density functions (pdf) on ${\mathbb S}^{p-1}$ is also introduced. Such processes are then studied in the case where the scattering distribution is von Mises Fisher (vMF). Asymptotic distributions for the multiconvolution of vMFs on ${\mathbb S}^{p-1}$ are obtained. Both Fourier expansion and asymptotic approximation allows us to compute estimation bounds for the parameters of Compound Cox Processes (CCP) on ${\mathbb S}^{p-1}$.
Maximum Hands-Off Control: A Paradigm of Control Effort Minimization
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a new paradigm of control, called a maximum hands-off control. A hands-off control is defined as a control that has a short support per unit time. The maximum hands-off control is the minimum support (or sparsest) per unit time among all controls that achieve control objectives. For finite horizon control, we show the equivalence between the maximum hands-off control and L1-optimal control under a uniqueness assumption called normality. This result rationalizes the use of L1 optimality in computing a maximum hands-off control. We also propose an L1/L2-optimal control to obtain a smooth hands-off control. Furthermore, we give a self-triggered feedback control algorithm for linear time-invariant systems, which achieves a given sparsity rate and practical stability in the case of plant disturbances. An example is included to illustrate the effectiveness of the proposed control.
On Data Preconditioning for Regularized Loss Minimization
Venue: arXiv cs.NA 2015
Year: 2015

In this work, we study data preconditioning, a well-known and long-existing technique, for boosting the convergence of first-order methods for regularized loss minimization. It is well understood that the condition number of the problem, i.e., the ratio of the Lipschitz constant to the strong convexity modulus, has a harsh effect on the convergence of the first-order optimization methods. Therefore, minimizing a small regularized loss for achieving good generalization performance, yielding an ill conditioned problem, becomes the bottleneck for big data problems. We provide a theory on data preconditioning for regularized loss minimization. In particular, our analysis exhibits an appropriate data preconditioner and characterizes the conditions on the loss function and on the data under which data preconditioning can reduce the condition number and therefore boost the convergence for minimizing the regularized loss. To make the data preconditioning practically useful, we endeavor to employ and analyze a random sampling approach to efficiently compute the preconditioned data. The preliminary experiments validate our theory.
Bernoulli-Gaussian Approximate Message-Passing Algorithm for Compressed Sensing with 1D-Finite-Difference Sparsity
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes a fast approximate message-passing (AMP) algorithm for solving compressed sensing (CS) recovery problems with 1D-finite-difference sparsity in term of MMSE estimation. The proposed algorithm, named ssAMP-BGFD, is low-computational with its fast convergence and cheap per-iteration cost, providing phase transition nearly approaching to the state-of-the-art. The proposed algorithm is originated from a sum-product message-passing rule, applying a Bernoulli-Gaussian (BG) prior, seeking an MMSE solution. The algorithm construction includes not only the conventional AMP technique for the measurement fidelity, but also suggests a simplified message-passing method to promote the signal sparsity in finite-difference. Furthermore, we provide an EM-tuning methodology to learn the BG prior parameters, suggesting how to use some practical measurement matrices satisfying the RIP requirement under the ssAMP-BGFD recovery. Extensive empirical results confirms performance of the proposed algorithm, in phase transition, convergence speed, and CPU runtime, compared to the recent algorithms.
Gaussian Interference Channel with Intermittent Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We investigate how to exploit intermittent feedback for interference management by studying the two-user Gaussian interference channel (IC). We approximately characterize (within a universal constant) the capacity region for the Gaussian IC with intermittent feedback. We exactly characterize the the capacity region of the linear deterministic version of the problem, which gives us insight into the Gaussian problem. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. We find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap. In contrast to other schemes developed for interference channel with feedback, our achievable scheme makes use of quantize-map-and-forward to relay the information obtained through feedback, performs forward decoding, and does not use structured codes. We also develop new outer bounds enabling us to obtain the (approximate) characterization of the capacity region.
Universal sketches for the frequency negative moments and other decreasing streaming sums
Venue: arXiv cs.DS 2015
Year: 2015

Given a stream with frequencies $f_d$, for $d\in[n]$, we characterize the space necessary for approximating the frequency negative moments $F_p=\sum |f_d|^p$, where $p<0$ and the sum is taken over all items $d\in[n]$ with nonzero frequency, in terms of $n$, $ε$, and $m=\sum |f_d|$. To accomplish this, we actually prove a much more general result. Given any nonnegative and nonincreasing function $g$, we characterize the space necessary for any streaming algorithm that outputs a $(1\pmε)$-approximation to $\sum g(|f_d|)$, where again the sum is over items with nonzero frequency. The storage required is expressed in the form of the solution to a relatively simple nonlinear optimization problem, and the algorithm is universal for $(1\pmε)$-approximations to any such sum where the applied function is nonnegative, nonincreasing, and has the same or smaller space complexity as $g$. This partially answers an open question of Nelson (IITK Workshop Kanpur, 2009).
Hierarchical Saliency Detection on Extended CSSD
Venue: arXiv cs.CV 2015
Year: 2015

Complex structures commonly exist in natural images. When an image contains small-scale high-contrast patterns either in the background or foreground, saliency detection could be adversely affected, resulting erroneous and non-uniform saliency assignment. The issue forms a fundamental challenge for prior methods. We tackle it from a scale point of view and propose a multi-layer approach to analyze saliency cues. Different from varying patch sizes or downsizing images, we measure region-based scales. The final saliency values are inferred optimally combining all the saliency cues in different scales using hierarchical inference. Through our inference model, single-scale information is selected to obtain a saliency map. Our method improves detection quality on many images that cannot be handled well traditionally. We also construct an extended Complex Scene Saliency Dataset (ECSSD) to include complex but general natural images.
Enhanced usage of keys obtained by physical, unconditionally secure distributions
Venue: arXiv cs.CR 2015
Year: 2015

Unconditionally secure physical key distribution schemes are very slow, and it is practically impossible to use a one-time-pad based cipher to guarantee unconditional security for the encryption of data because using the key bits more than once gives out statistical information, for example via the known-plain-text-attack or by utilizing known components of the protocol and language statistics. Here we outline a protocol that reduces this speed problem and allows almost-one-time-pad based communication with an unconditionally secure physical key of finite length. The physical, unconditionally secure key is not used for data encryption but is employed in order to generate and share a new software-based key without any known-plain-text component. The software-only-based key distribution is then changed from computationally secure to unconditionally secure, because the communicated key-exchange data (algorithm parameters, one-way functions of random numbers, etc.) are encrypted in an unconditionally secure way with a one-time-pad. For practical applications, this combined physical/software key distribution based communication looks favorable compared to the software-only and physical-only key distribution based communication whenever the speed of the physical key distribution is much lower than that of the software-based key distribution. A mathematical security proof of this new scheme remains an open problem.
Unicast Barrage Relay Networks: Outage Analysis and Optimization
Venue: arXiv cs.NI 2015
Year: 2015

Barrage relays networks (BRNs) are ad hoc networks built on a rapid cooperative flooding primitive as opposed to the traditional point-to-point link abstraction. Controlled barrage regions (CBRs) can be used to contain this flooding primitive for unicast and multicast, thereby enabling spatial reuse. In this paper, the behavior of individual CBRs is described as a Markov process that models the potential cooperative relay transmissions. The outage probability for a CBR is found in closed form for a given topology, and the probability takes into account fading and co-channel interference (CCI) between adjacent CBRs. Having adopted this accurate analytical framework, this paper proceeds to optimize a BRN by finding the optimal size of each CBR, the number of relays contained within each CBR, the optimal relay locations when they are constrained to lie on a straight line, and the code rate that maximizes the transport capacity.
Planar Induced Subgraphs of Sparse Graphs
Venue: arXiv cs.CG 2015
Year: 2015

We show that every graph has an induced pseudoforest of at least $n-m/4.5$ vertices, an induced partial 2-tree of at least $n-m/5$ vertices, and an induced planar subgraph of at least $n-m/5.2174$ vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest $K_h$-minor-free graph in a given graph can sometimes be at most $n-m/6+o(m)$.
Robust Geometry Estimation using the Generalized Voronoi Covariance Measure
Venue: arXiv cs.CG 2015
Year: 2015

The Voronoi Covariance Measure of a compact set K of R^d is a tensor-valued measure that encodes geometric information on K and which is known to be resilient to Hausdorff noise but sensitive to outliers. In this article, we generalize this notion to any distance-like function delta and define the delta-VCM. We show that the delta-VCM is resilient to Hausdorff noise and to outliers, thus providing a tool to estimate robustly normals from a point cloud approximation. We present experiments showing the robustness of our approach for normal and curvature estimation and sharp feature detection.
A Comparative Study of Programming Languages in Rosetta Code
Venue: arXiv cs.SE 2015
Year: 2015

Sometimes debates on programming languages are more religious than scientific. Questions about which language is more succinct or efficient, or makes developers more productive are discussed with fervor, and their answers are too often based on anecdotes and unsubstantiated beliefs. In this study, we use the largely untapped research potential of Rosetta Code, a code repository of solutions to common programming tasks in various languages, to draw a fair and well-founded comparison. Rosetta Code offers a large data set for analysis. Our study is based on 7087 solution programs corresponding to 745 tasks in 8 widely used languages representing the major programming paradigms (procedural: C and Go; object-oriented: C# and Java; functional: F# and Haskell; scripting: Python and Ruby). Our statistical analysis reveals, most notably, that: functional and scripting languages are more concise than procedural and object-oriented languages; C is hard to beat when it comes to raw speed on large inputs, but performance differences over inputs of moderate size are less pronounced and allow even interpreted languages to be competitive; compiled strongly-typed languages, where more defects can be caught at compile time, are less prone to runtime failures than interpreted or weakly-typed languages. We discuss implications of these results for developers, language designers, and educators.