OpenRaiser/Intern-Atlas huggingface dataset:
Robust Spectral Compressed Sensing via Structured Matrix Completion
Venue: arXiv cs.IT 2014
Year: 2014

The paper explores the problem of \emph{spectral compressed sensing}, which aims to recover a spectrally sparse signal from a small random subset of its $n$ time domain samples. The signal of interest is assumed to be a superposition of $r$ multi-dimensional complex sinusoids, while the underlying frequencies can assume any \emph{continuous} values in the normalized frequency domain. Conventional compressed sensing paradigms suffer from the basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this issue, we develop a novel algorithm, called \emph{Enhanced Matrix Completion (EMaC)}, based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multi-fold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of $r\log^{4}n$, and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC still allows exact recovery, provided that the sample complexity exceeds the order of $r^{2}\log^{3}n$. Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multi-fold Hankel or Toeplitz matrix from minimal observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments.
Quantile Regression for Large-scale Applications
Venue: arXiv cs.DS 2014
Year: 2014

Quantile regression is a method to estimate the quantiles of the conditional distribution of a response variable, and as such it permits a much more accurate portrayal of the relationship between the response variable and observed covariates than methods such as Least-squares or Least Absolute Deviations regression. It can be expressed as a linear program, and, with appropriate preprocessing, interior-point methods can be used to find a solution for moderately large problems. Dealing with very large problems, \emph(e.g.), involving data up to and beyond the terabyte regime, remains a challenge. Here, we present a randomized algorithm that runs in nearly linear time in the size of the input and that, with constant probability, computes a $(1+ε)$ approximate solution to an arbitrary quantile regression problem. As a key step, our algorithm computes a low-distortion subspace-preserving embedding with respect to the loss function of quantile regression. Our empirical evaluation illustrates that our algorithm is competitive with the best previous work on small to medium-sized problems, and that in addition it can be implemented in MapReduce-like environments and applied to terabyte-sized problems.
Study of Network Migration to New Technologies using Agent-based Modeling Techniques
Venue: arXiv cs.NI 2014
Year: 2014

Conventionally, network migration models study competition between emerging and incumbent technologies by considering the resulting increase in revenue and associated cost of migration. We propose to advance the science in the existing network migration models by considering additional critical factors, including (i) synergistic relationships across multiple technologies, (ii) reduction in operational expenditures (OpEx) as a reason to migrate, and, (iii) implications of local network effects on migration decisions. To this end, we propose a novel agent-based migration model considering these factors. Based on the model, we analyze the case study of network migration to two emerging networking paradigms, i.e., IETF Path Computation Element (PCE) and Software-Defined Networking (SDN). We validate our model using extensive simulations. Our results demonstrate the synergistic effects of migration to multiple complementary technologies, and show that a technology migration may be eased by the joint migration to multiple technologies. In particular, we find that migration to SDN can be eased by joint migration to PCE, and that the benefits derived from SDN are best exploited in combination with PCE, than by itself.
Real-Time Welfare-Maximizing Regulation Allocation in Dynamic Aggregator-EVs System
Venue: arXiv cs.SY 2014
Year: 2014

The concept of vehicle-to-grid (V2G) has gained recent interest as more and more electric vehicles (EVs) are put to use. In this paper, we consider a dynamic aggregator-EVs system, where an aggregator centrally coordinates a large number of dynamic EVs to perform regulation service. We propose a Welfare-Maximizing Regulation Allocation (WMRA) algorithm for the aggregator to fairly allocate the regulation amount among its EVs. Compared to previous works, WMRA accommodates a wide spectrum of vital system characteristics, including dynamics of EV, limited EV battery size, EV battery degradation cost, and the cost of using external energy sources for the aggregator. The algorithm operates in real time and does not require any prior knowledge of the statistical information of the system. Theoretically, we demonstrate that WMRA is away from the optimum by O(1/V), where V is a controlling parameter depending on EV's battery size. In addition, our simulation results indicate that WMRA can substantially outperform a suboptimal greedy algorithm.
On Improved Bounds on Bounded Degree Spanning Trees for Points in Arbitrary Dimension
Venue: arXiv cs.CG 2014
Year: 2014

Given points in Euclidean space of arbitrary dimension, we prove that there exists a spanning tree having no vertices of degree greater than 3 with weight at most 1.559 times the weight of the minimum spanning tree. We also prove that there is a set of points such that no spanning tree of maximal degree 3 exists that has this ratio be less than 1.447. Our central result is based on the proof of the following claim: Given $n$ points in Euclidean space with one special point $V$, there exists a Hamiltonian path with an endpoint at $V$ that is at most 1.559 times longer than the sum of the distances of the points to $V$. These proofs also lead to a way to find the tree in linear time given the minimal spanning tree.
Phaseless Signal Recovery in Infinite Dimensional Spaces using Structured Modulations
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers the recovery of continuous signals in infinite dimensional spaces from the magnitude of their frequency samples. It proposes a sampling scheme which involves a combination of oversampling and modulations with complex exponentials. Sufficient conditions are given such that almost every signal with compact support can be reconstructed up to a unimodular constant using only its magnitude samples in the frequency domain. Finally it is shown that an average sampling rate of four times the Nyquist rate is enough to reconstruct almost every time-limited signal.
Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories
Venue: arXiv cs.DB 2014
Year: 2014

Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their application in spatio-temporal data analysis. Recent work has considered the realistic case where the trajectories are uncertain; however, only simple uncertainty models have been proposed, which do not allow for accurate probabilistic search. In this paper, we fill this gap by addressing probabilistic nearest neighbor queries in databases with uncertain trajectories modeled by stochastic processes, specifically the Markov chain model. We study three nearest neighbor query semantics that take as input a query state or trajectory $q$ and a time interval. For some queries, we show that no polynomial time solution can be found. For problems that can be solved in PTIME, we present exact query evaluation algorithms, while for the general case, we propose a sophisticated sampling approach, which uses Bayesian inference to guarantee that sampled trajectories conform to the observation data stored in the database. This sampling approach can be used in Monte-Carlo based approximation solutions. We include an extensive experimental study to support our theoretical results.
Contractive De-noising Auto-encoder
Venue: arXiv cs.LG 2014
Year: 2014

Auto-encoder is a special kind of neural network based on reconstruction. De-noising auto-encoder (DAE) is an improved auto-encoder which is robust to the input by corrupting the original data first and then reconstructing the original input by minimizing the reconstruction error function. And contractive auto-encoder (CAE) is another kind of improved auto-encoder to learn robust feature by introducing the Frobenius norm of the Jacobean matrix of the learned feature with respect to the original input. In this paper, we combine de-noising auto-encoder and contractive auto- encoder, and propose another improved auto-encoder, contractive de-noising auto- encoder (CDAE), which is robust to both the original input and the learned feature. We stack CDAE to extract more abstract features and apply SVM for classification. The experiment result on benchmark dataset MNIST shows that our proposed CDAE performed better than both DAE and CAE, proving the effective of our method.
An analysis of block sampling strategies in compressed sensing
Venue: arXiv cs.IT 2014
Year: 2014

Compressed sensing is a theory which guarantees the exact recovery of sparse signals from a small number of linear projections. The sampling schemes suggested by current compressed sensing theories are often of little practical relevance since they cannot be implemented on real acquisition systems. In this paper, we study a new random sampling approach that consists in projecting the signal over blocks of sensing vectors. A typical example is the case of blocks made of horizontal lines in the 2D Fourier plane. We provide theoretical results on the number of blocks that are required for exact sparse signal reconstruction. This number depends on two properties named intra and inter-support block coherence. We then show through a series of examples including Gaussian measurements, isolated measurements or blocks in time-frequency bases, that the main result is sharp in the sense that the minimum amount of blocks necessary to reconstruct sparse signals cannot be improved up to a multiplicative logarithmic factor. The proposed results provide a good insight on the possibilities and limits of block compressed sensing in imaging devices such as magnetic resonance imaging, radio-interferometry or ultra-sound imaging.
Large-System Analysis of Correlated MIMO Multiple Access Channels with Arbitrary Signaling in the Presence of Interference
Venue: arXiv cs.IT 2014
Year: 2014

Presence of multiple antennas on both sides of a communication channel promises significant improvements in system throughput and power efficiency. In effect, a new class of large multiple-input multiple-output (MIMO) communication systems has recently emerged and attracted both scientific and industrial attention. To analyze these systems in realistic scenarios, one has to include such aspects as co-channel interference, multiple access and spatial correlation. In this paper, we study the properties of correlated MIMO multiple-access channels in the presence of external interference. Using the replica method from statistical physics, we derive the ergodic sum-rate of the communication for arbitrary signal constellations when the numbers of antennas at both ends of the channel grow large. Based on these asymptotic expressions, we also address the problem of sum-rate maximization using statistical channel information and linear precoding. The numerical results demonstrate that when the interfering terminals use discrete constellations, the resulting interference becomes easier to handle compared to Gaussian signals. Thus, it may be possible to accommodate more interfering transmitter-receiver pairs within the same area as compared to the case of Gaussian signals. In addition, we demonstrate numerically for the Gaussian and QPSK signaling schemes that it is possible to design precoder matrices that significantly improve the achievable rates at low-to-mid range of signal-to-noise ratios when compared to isotropic precoding.
Asynchronous BFT Storage with 2t+1 Data Replicas
Venue: arXiv cs.DC 2014
Year: 2014

The cost of Byzantine Fault Tolerant (BFT) storage is the main concern preventing its adoption in practice. This cost stems from the need to maintain at least 3t+1 replicas in different storage servers in the asynchronous model, so that t Byzantine replica faults can be tolerated. In this paper, we present MDStore, the first fully asynchronous read/write BFT storage protocol that reduces the number of data replicas to as few as 2t+1, maintaining 3t+1 replicas of metadata at (possibly) different servers. At the heart of MDStore store is its metadata service that is built upon a new abstraction we call timestamped storage. Timestamped storage both allows for conditional writes (facilitating the implementation of a metadata service) and has consensus number one (making it implementable wait-free in an asynchronous system despite faults). In addition to its low data replication factor, MDStore offers very strong guarantees implementing multi-writer multi-reader atomic wait-free semantics and tolerating any number of Byzantine readers and crash-faulty writers. We further show that MDStore data replication overhead is optimal; namely, we prove a lower bound of 2t+1 on the number of data replicas that applies even to crash-tolerant storage with a fault-free metadata service oracle. Finally, we prove that separating data from metadata for reducing the cost of BFT storage is not possible without cryptographic assumptions. However, our MDStore protocol uses only lightweight cryptographic hash functions.
A coercion-resistant protocol for conducting elections by telephone
Venue: arXiv cs.CR 2014
Year: 2014

We present a protocol that allows voters to phone in their votes. Our protocol makes it expensive for a candidate and a voter to cooperate to prove to the candidate who the voter voted for. When the electoral pool is large enough, the cost to the candidate of manipulating sufficiently many votes to have an influence on the election results becomes impossibly expensive. Hence, the protocol provides candidates no incentive to attempt inducement or coercion of voters, resulting in free and fair elections with the promise of cost savings and higher voter turnout over traditional elections. One major inadequacy with our suggested protocol is that we assume the existence of a trusted election authority to count the votes.
Near-Optimal Sensor Placement for Linear Inverse Problems
Venue: arXiv cs.IT 2014
Year: 2014

A classic problem is the estimation of a set of parameters from measurements collected by only a few sensors. The number of sensors is often limited by physical or economical constraints and their placement is of fundamental importance to obtain accurate estimates. Unfortunately, the selection of the optimal sensor locations is intrinsically combinatorial and the available approximation algorithms are not guaranteed to generate good solutions in all cases of interest. We propose FrameSense, a greedy algorithm for the selection of optimal sensor locations. The core cost function of the algorithm is the frame potential, a scalar property of matrices that measures the orthogonality of its rows. Notably, FrameSense is the first algorithm that is near-optimal in terms of mean square error, meaning that its solution is always guaranteed to be close to the optimal one. Moreover, we show with an extensive set of numerical experiments that FrameSense achieves state-of-the-art performance while having the lowest computational cost, when compared to other greedy methods.
Accuracy of Range-Based Cooperative Localization in Wireless Sensor Networks: A Lower Bound Analysis
Venue: arXiv cs.NI 2014
Year: 2014

Accurate location information is essential for many wireless sensor network (WSN) applications. A location-aware WSN generally includes two types of nodes: sensors whose locations to be determined and anchors whose locations are known a priori. For range-based localization, sensors' locations are deduced from anchor-to-sensor and sensor-to-sensor range measurements. Localization accuracy depends on the network parameters such as network connectivity and size. This paper provides a generalized theory that quantitatively characterizes such relation between network parameters and localization accuracy. We use the average degree as a connectivity metric and use geometric dilution of precision (DOP), equivalent to the Cramer-Rao bound, to quantify localization accuracy. We prove a novel lower bound on expectation of average geometric DOP (LB-E-AGDOP) and derives a closed-form formula that relates LB-E-AGDOP to only three parameters: average anchor degree, average sensor degree, and number of sensor nodes. The formula shows that localization accuracy is approximately inversely proportional to the average degree, and a higher ratio of average anchor degree to average sensor degree yields better localization accuracy. Furthermore, the paper demonstrates a strong connection between LB-E-AGDOP and the best achievable accuracy. Finally, we validate the theory via numerical simulations with three different random graph models.
Efficient and Robust Persistent Homology for Measures
Venue: arXiv cs.CG 2014
Year: 2014

We extend the notion of the distance to a measure from Euclidean space to probability measures on general metric spaces as a way to do topological data analysis in a way that is robust to noise and outliers. We then give an efficient way to approximate the sub-level sets of this function by a union of metric balls and extend previous results on sparse Rips filtrations to this setting. This robust and efficient approach to topological data analysis is illustrated with several examples from an implementation.
Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
Venue: arXiv cs.IT 2014
Year: 2014

We show that numerical approximations of Kolmogorov complexity (K) applied to graph adjacency matrices capture some group-theoretic and topological properties of graphs and empirical networks ranging from metabolic to social networks. That K and the size of the group of automorphisms of a graph are correlated opens up interesting connections to problems in computational geometry, and thus connects several measures and concepts from complexity science. We show that approximations of K characterise synthetic and natural networks by their generating mechanisms, assigning lower algorithmic randomness to complex network models (Watts-Strogatz and Barabasi-Albert networks) and high Kolmogorov complexity to (random) Erdos-Renyi graphs. We derive these results via two different Kolmogorov complexity approximation methods applied to the adjacency matrices of the graphs and networks. The methods used are the traditional lossless compression approach to Kolmogorov complexity, and a normalised version of a Block Decomposition Method (BDM) measure, based on algorithmic probability theory.
A Note on Graphs of Linear Rank-Width 1
Venue: arXiv cs.DM 2014
Year: 2014

We prove that a connected graph has linear rank-width 1 if and only if it is a distance-hereditary graph and its split decomposition tree is a path. An immediate consequence is that one can decide in linear time whether a graph has linear rank-width at most 1, and give an obstruction if not. Other immediate consequences are several characterisations of graphs of linear rank-width 1. In particular a connected graph has linear rank-width 1 if and only if it is locally equivalent to a caterpillar if and only if it is a vertex-minor of a path [O-joung Kwon and Sang-il Oum, Graphs of small rank-width are pivot-minors of graphs of small tree-width, arxiv:1203.3606] if and only if it does not contain the co-K_2 graph, the Net graph and the 5-cycle graph as vertex-minors [Isolde Adler, Arthur M. Farley and Andrzej Proskurowski, Obstructions for linear rank-width at most 1, arxiv:1106.2533].
Happy Edges: Threshold-Coloring of Regular Lattices
Venue: arXiv cs.DS 2014
Year: 2014

We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into {\em near} and {\em far} sets and an integer threshold $t$, a {\em threshold-coloring} of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by $t$ or less, while endpoints of far edges differ by more than $t$. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable.
Solvability of Cubic Graphs - From Four Color Theorem to NP-Complete
Venue: arXiv cs.DM 2014
Year: 2014

Similar to Euclidean geometry, graph theory is a science that studies figures that consist of points and lines. The core of Euclidean geometry is the parallel postulate, which provides the basis of the geometric invariant that the sum of the angles in every triangle equals $π$ and Cramer's rule for solving simultaneous linear equations. Since the counterpart of parallel postulate in graph theory is not known, which could be the reason that two similar problems in graph theory, namely the four color theorem (a topological invariant) and the solvability of NP-complete problems (discrete simultaneous equations), remain open to date. In this paper, based on the complex coloring of cubic graphs, we propose the reducibility postulate of the Petersen configuration to fill this gap. Comparing edge coloring with a system of linear equations, we found that the postulate of reducibility in graph theory and the parallel postulate in Euclidean geometry share some common characteristics of the plane. First, they both provide solvability conditions on two equations in the plane. Second, the two basic invariants of the plane, namely the chromatic index of bridgeless cubic plane graphs and the sum of the angles in every triangle, can be respectively deduced from them in a straightforward manner. This reducibility postulation has been verified by more than one hundred thousand instances of Peterson configurations generated by computer. Despite that, we still don't have a logical proof of this assertion. Similar to that of the parallel postulate, we tend to think that describing these natural laws by even more elementary properties of the plane is inconceivable.
Learning to encode motion using spatio-temporal synchrony
Venue: arXiv cs.CV 2014
Year: 2014

We consider the task of learning to extract motion from videos. To this end, we show that the detection of spatial transformations can be viewed as the detection of synchrony between the image sequence and a sequence of features undergoing the motion we wish to detect. We show that learning about synchrony is possible using very fast, local learning rules, by introducing multiplicative "gating" interactions between hidden units across frames. This makes it possible to achieve competitive performance in a wide variety of motion estimation tasks, using a small fraction of the time required to learn features, and to outperform hand-crafted spatio-temporal features by a large margin. We also show how learning about synchrony can be viewed as performing greedy parameter estimation in the well-known motion energy model.