OpenRaiser/Intern-Atlas huggingface dataset:
On Design Mining: Coevolution and Surrogate Models
Venue: arXiv cs.NE 2016
Year: 2016

Design mining is the use of computational intelligence techniques to iteratively search and model the attribute space of physical objects evaluated directly through rapid prototyping to meet given objectives. It enables the exploitation of novel materials and processes without formal models or complex simulation. In this paper, we focus upon the coevolutionary nature of the design process when it is decomposed into concurrent sub-design threads due to the overall complexity of the task. Using an abstract, tuneable model of coevolution we consider strategies to sample sub-thread designs for whole system testing and how best to construct and use surrogate models within the coevolutionary scenario. Drawing on our findings, the paper then describes the effective design of an array of six heterogeneous vertical-axis wind turbines.
Evolving NoSQL Databases Without Downtime
Venue: arXiv cs.DB 2016
Year: 2016

NoSQL databases like Redis, Cassandra, and MongoDB are increasingly popular because they are flexible, lightweight, and easy to work with. Applications that use these databases will evolve over time, sometimes necessitating (or preferring) a change to the format or organization of the data. The problem we address in this paper is: How can we support the evolution of high-availability applications and their NoSQL data online, without excessive delays or interruptions, even in the presence of backward-incompatible data format changes? We present KVolve, an extension to the popular Redis NoSQL database, as a solution to this problem. KVolve permits a developer to submit an upgrade specification that defines how to transform existing data to the newest version. This transformation is applied lazily as applications interact with the database, thus avoiding long pause times. We demonstrate that KVolve is expressive enough to support substantial practical updates, including format changes to RedisFS, a Redis-backed file system, while imposing essentially no overhead in general use and minimal pause times during updates.
Low-latency compression of mocap data using learned spatial decorrelation transform
Venue: arXiv cs.MM 2016
Year: 2016

Due to the growing needs of human motion capture (mocap) in movie, video games, sports, etc., it is highly desired to compress mocap data for efficient storage and transmission. This paper presents two efficient frameworks for compressing human mocap data with low latency. The first framework processes the data in a frame-by-frame manner so that it is ideal for mocap data streaming and time critical applications. The second one is clip-based and provides a flexible tradeoff between latency and compression performance. Since mocap data exhibits some unique spatial characteristics, we propose a very effective transform, namely learned orthogonal transform (LOT), for reducing the spatial redundancy. The LOT problem is formulated as minimizing square error regularized by orthogonality and sparsity and solved via alternating iteration. We also adopt a predictive coding and temporal DCT for temporal decorrelation in the frame- and clip-based frameworks, respectively. Experimental results show that the proposed frameworks can produce higher compression performance at lower computational cost and latency than the state-of-the-art methods.
Long-Range Motion Trajectories Extraction of Articulated Human Using Mesh Evolution
Venue: arXiv cs.CV 2016
Year: 2016

This letter presents a novel approach to extract reliable dense and long-range motion trajectories of articulated human in a video sequence. Compared with existing approaches that emphasize temporal consistency of each tracked point, we also consider the spatial structure of tracked points on the articulated human. We treat points as a set of vertices, and build a triangle mesh to join them in image space. The problem of extracting long-range motion trajectories is changed to the issue of consistency of mesh evolution over time. First, self-occlusion is detected by a novel mesh-based method and an adaptive motion estimation method is proposed to initialize mesh between successive frames. Furthermore, we propose an iterative algorithm to efficiently adjust vertices of mesh for a physically plausible deformation, which can meet the local rigidity of mesh and silhouette constraints. Finally, we compare the proposed method with the state-of-the-art methods on a set of challenging sequences. Evaluations demonstrate that our method achieves favorable performance in terms of both accuracy and integrity of extracted trajectories.
Subspace Estimation and Decomposition for Large Millimeter-Wave MIMO systems
Venue: arXiv cs.IT 2016
Year: 2016

Channel estimation and precoding in hybrid analog-digital millimeter-wave (mmWave) MIMO systems is a fundamental problem that has yet to be addressed, before any of the promised gains can be harnessed. For that matter, we propose a method (based on the well-known Arnoldi iteration) exploiting channel reciprocity in TDD systems and the sparsity of the channel's eigenmodes, to estimate the right (resp. left) singular subspaces of the channel, at the BS (resp. MS). We first describe the algorithm in the context of conventional MIMO systems, and derive bounds on the estimation error in the presence of distortions at both BS and MS. We later identify obstacles that hinder the application of such an algorithm to the hybrid analog-digital architecture, and address them individually. In view of fulfilling the constraints imposed by the hybrid analog-digital architecture, we further propose an iterative algorithm for subspace decomposition, whereby the above estimated subspaces, are approximated by a cascade of analog and digital precoder / combiner. Finally, we evaluate the performance of our scheme against the perfect CSI, fully digital case (i.e., an equivalent conventional MIMO system), and conclude that similar performance can be achieved, especially at medium-to-high SNR (where the performance gap is less than 5%), however, with a drastically lower number of RF chains (4 to 8 times less).
Sticky Seeding in Discrete-Time Reversible-Threshold Networks
Venue: arXiv cs.SI 2016
Year: 2016

When nodes can repeatedly update their behavior (as in agent-based models from computational social science or repeated-game play settings) the problem of optimal network seeding becomes very complex. For a popular spreading-phenomena model of binary-behavior updating based on thresholds of adoption among neighbors, we consider several planning problems in the design of \textit{Sticky Interventions}: when adoption decisions are reversible, the planner aims to find a Seed Set where temporary intervention leads to long-term behavior change. We prove that completely converting a network at minimum cost is $Ω(\ln (OPT) )$-hard to approximate and that maximizing conversion subject to a budget is $(1-\frac{1}{e})$-hard to approximate. Optimization heuristics which rely on many objective function evaluations may still be practical, particularly in relatively-sparse networks: we prove that the long-term impact of a Seed Set can be evaluated in $O(|E|^2)$ operations. For a more descriptive model variant in which some neighbors may be more influential than others, we show that under integer edge weights from $\{0,1,2,...,k\}$ objective function evaluation requires only $O(k|E|^2)$ operations. These operation bounds are based on improvements we give for bounds on time-steps-to-convergence under discrete-time reversible-threshold updates in networks.
A Geometric Approach to Fault Detection and Isolation of Two-Dimensional (2D) Systems
Venue: arXiv cs.SY 2016
Year: 2016

In this work, we develop a novel fault detection and isolation (FDI) scheme for discrete-time two-dimensional (2D) systems that are represented by the Fornasini-Marchesini model II (FMII). This is accomplished by generalizing the basic invariant subspaces including unobservable, conditioned invariant and unobservability subspaces of 1D systems to 2D models. These extensions have been achieved and facilitated by representing a 2D model as an infinite dimensional (Inf-D) system on a Banach vector space, and by particularly constructing algorithms that compute these subspaces in a \emph{finite and known} number of steps. By utilizing the introduced subspaces the FDI problem is formulated and necessary and sufficient conditions for its solvability are provided. Sufficient conditions for solvability of the FDI problem for 2D systems using both deadbeat and LMI filters are also developed. Moreover, the capabilities and advantages of our proposed approach are demonstrated by performing an analytical comparison with the currently available 2D geometric methods in the literature. Finally, numerical simulations corresponding to an approximation of a hyperbolic partial differential equation (PDE) system of a heat exchanger, that is mathematically represented as a 2D model, have also been provided.
Distributed Algorithms for Computation of Centrality Measures in Complex Networks
Venue: arXiv cs.SY 2016
Year: 2016

This paper is concerned with distributed computation of several commonly used centrality measures in complex networks. In particular, we propose deterministic algorithms, which converge in finite time, for the distributed computation of the degree, closeness and betweenness centrality measures in directed graphs. Regarding eigenvector centrality, we consider the PageRank problem as its typical variant, and design distributed randomized algorithms to compute PageRank for both fixed and time-varying graphs. A key feature of the proposed algorithms is that they do not require to know the network size, which can be simultaneously estimated at every node, and that they are clock-free. To address the PageRank problem of time-varying graphs, we introduce the novel concept of persistent graph, which eliminates the effect of spamming nodes. Moreover, we prove that these algorithms converge almost surely and in the sense of $L^p$. Finally, the effectiveness of the proposed algorithms is illustrated via extensive simulations using a classical benchmark.
Optimal approximate matrix product in terms of stable rank
Venue: arXiv cs.DS 2016
Year: 2016

We prove, using the subspace embedding guarantee in a black box way, that one can achieve the spectral norm guarantee for approximate matrix multiplication with a dimensionality-reducing map having $m = O(\tilde{r}/\varepsilon^2)$ rows. Here $\tilde{r}$ is the maximum stable rank, i.e. squared ratio of Frobenius and operator norms, of the two matrices being multiplied. This is a quantitative improvement over previous work of [MZ11, KVZ14], and is also optimal for any oblivious dimensionality-reducing map. Furthermore, due to the black box reliance on the subspace embedding property in our proofs, our theorem can be applied to a much more general class of sketching matrices than what was known before, in addition to achieving better bounds. For example, one can apply our theorem to efficient subspace embeddings such as the Subsampled Randomized Hadamard Transform or sparse subspace embeddings, or even with subspace embedding constructions that may be developed in the future. Our main theorem, via connections with spectral error matrix multiplication shown in prior work, implies quantitative improvements for approximate least squares regression and low rank approximation. Our main result has also already been applied to improve dimensionality reduction guarantees for $k$-means clustering [CEMMP14], and implies new results for nonparametric regression [YPW15]. We also separately point out that the proof of the "BSS" deterministic row-sampling result of [BSS12] can be modified to show that for any matrices $A, B$ of stable rank at most $\tilde{r}$, one can achieve the spectral norm guarantee for approximate matrix multiplication of $A^T B$ by deterministically sampling $O(\tilde{r}/\varepsilon^2)$ rows that can be found in polynomial time. The original result of [BSS12] was for rank instead of stable rank. Our observation leads to a stronger version of a main theorem of [KMST10].
Multi-Type Activity Recognition in Robot-Centric Scenarios
Venue: arXiv cs.CV 2016
Year: 2016

Activity recognition is very useful in scenarios where robots interact with, monitor or assist humans. In the past years many types of activities -- single actions, two persons interactions or ego-centric activities, to name a few -- have been analyzed. Whereas traditional methods treat such types of activities separately, an autonomous robot should be able to detect and recognize multiple types of activities to effectively fulfill its tasks. We propose a method that is intrinsically able to detect and recognize activities of different types that happen in sequence or concurrently. We present a new unified descriptor, called Relation History Image (RHI), which can be extracted from all the activity types we are interested in. We then formulate an optimization procedure to detect and recognize activities of different types. We apply our approach to a new dataset recorded from a robot-centric perspective and systematically evaluate its quality compared to multiple baselines. Finally, we show the efficacy of the RHI descriptor on publicly available datasets performing extensive comparisons.
Constacyclic codes over F_q + u F_q + v F_q + u v F_q
Venue: arXiv cs.IT 2016
Year: 2016

Let q be a prime power and F_q be a finite field. In this paper, we study constacyclic codes over the ring F_q+ u F_q +v F_q+ u v F_q, where u^2=u, v^2=v and uv=vu. We characterized the generator polynomials of constacyclic codes and their duals using some decomposition of this ring. We also define a gray map and characterize the Gray images of self-dual cyclic codes over F_q+uF_q+vF_q+uvF_q.
On the Maximum Rate of Networked Computation in a Capacitated Network
Venue: arXiv cs.DC 2016
Year: 2016

Given a capacitated communication network $\mathcal{N}$ and a function f that needs to be computed on $\mathcal{N},$ we study the problem of generating a computation and communication schedule in $\mathcal{N}$ to maximize the rate of computation of f. Shah et. al.[IEEE Journal of Selected Areas in Communication, 2013] studied this problem when the computation schema $\mathcal{G}$ for f is a tree. We define the notion of a schedule when $\mathcal{G}$ is a general DAG and show that finding an optimal schedule is equivalent to finding the solution of a packing LP. We prove that approximating the maximum rate is MAX SNP-hard by looking at the packing LP. For this packing LP we prove that solving the separation oracle of its dual is equivalent to solving the LP. The separation oracle of the dual reduces to the problem of finding minimum cost embedding given $\mathcal{N},\mathcal{G},$ which we prove to be MAX SNP-hard even when $\mathcal{G}$ has bounded degree and bounded edge weights and $\mathcal{N}$ has just three vertices. We present a polynomial time algorithm to compute the maximum rate of function computation when $\mathcal{N}$ has two vertices by reducing the problem to a version of submodular function minimization problem. For the general $\mathcal{N}$ we study restricted class of schedules and its equivalent packing LP. We observe that for this packing LP also the separation oracle of its dual reduces to finding minimum cost embedding. A version of this minimum cost embedding problem has been studied in literature. We present a quadratic integer program for the minimum cost embedding problem and its linear programming relaxation based on earthmover metric. We also present some approximate algorithms for special classes of $\mathcal{G}.$
Near Maximum-Likelihood Detector and Channel Estimator for Uplink Multiuser Massive MIMO Systems with One-Bit ADCs
Venue: arXiv cs.IT 2016
Year: 2016

In massive multiple-input multiple-output (MIMO) systems, it may not be power efficient to have a high-resolution analog-to-digital converter (ADC) for each antenna element. In this paper, a near maximum likelihood (nML) detector for uplink multiuser massive MIMO systems is proposed where each antenna is connected to a pair of one-bit ADCs, i.e., one for each real and imaginary component of the baseband signal. The exhaustive search over all the possible transmitted vectors required in the original maximum likelihood (ML) detection problem is relaxed to formulate an ML estimation problem. Then, the ML estimation problem is converted into a convex optimization problem which can be efficiently solved. Using the solution, the base station can perform simple symbol-by-symbol detection for the transmitted signals from multiple users. To further improve detection performance, we also develop a two-stage nML detector that exploits the structures of both the original ML and the proposed (one-stage) nML detectors. Numerical results show that the proposed nML detectors are efficient enough to simultaneously support multiple uplink users adopting higher-order constellations, e.g., 16 quadrature amplitude modulation. Since our detectors exploit the channel state information as part of the detection, an ML channel estimation technique with one-bit ADCs that shares the same structure with our proposed nML detector is also developed. The proposed detectors and channel estimator provide a complete low power solution for the uplink of a massive MIMO system.
The Bernstein Mechanism: Function Release under Differential Privacy
Venue: arXiv cs.DS 2016
Year: 2016

We address the problem of general function release under differential privacy, by developing a functional mechanism that applies under the weak assumptions of oracle access to target function evaluation and sensitivity. These conditions permit treatment of functions described explicitly or implicitly as algorithmic black boxes. We achieve this result by leveraging the iterated Bernstein operator for polynomial approximation of the target function, and polynomial coefficient perturbation. Under weak regularity conditions, we establish fast rates on utility measured by high-probability uniform approximation. We provide a lower bound on the utility achievable for any functional mechanism that is $\varepsilon$-differentially private. The generality of our mechanism is demonstrated by the analysis of a number of example learners, including naive Bayes, non-parametric estimators and regularized empirical risk minimization. Competitive rates are demonstrated for kernel density estimation; and $\varepsilon$-differential privacy is achieved for a broader class of support vector machines than known previously.
Learning to classify with possible sensor failures
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we propose a general framework to learn a robust large-margin binary classifier when corrupt measurements, called anomalies, caused by sensor failure might be present in the training set. The goal is to minimize the generalization error of the classifier on non-corrupted measurements while controlling the false alarm rate associated with anomalous samples. By incorporating a non-parametric regularizer based on an empirical entropy estimator, we propose a Geometric-Entropy-Minimization regularized Maximum Entropy Discrimination (GEM-MED) method to learn to classify and detect anomalies in a joint manner. We demonstrate using simulated data and a real multimodal data set. Our GEM-MED method can yield improved performance over previous robust classification methods in terms of both classification accuracy and anomaly detection rate.
Multi-Face Tracking by Extended Bag-of-Tracklets in Egocentric Videos
Venue: arXiv cs.CV 2016
Year: 2016

Wearable cameras offer a hands-free way to record egocentric images of daily experiences, where social events are of special interest. The first step towards detection of social events is to track the appearance of multiple persons involved in it. In this paper, we propose a novel method to find correspondences of multiple faces in low temporal resolution egocentric videos acquired through a wearable camera. This kind of photo-stream imposes additional challenges to the multi-tracking problem with respect to conventional videos. Due to the free motion of the camera and to its low temporal resolution, abrupt changes in the field of view, in illumination condition and in the target location are highly frequent. To overcome such difficulties, we propose a multi-face tracking method that generates a set of tracklets through finding correspondences along the whole sequence for each detected face and takes advantage of the tracklets redundancy to deal with unreliable ones. Similar tracklets are grouped into the so called extended bag-of-tracklets (eBoT), which is aimed to correspond to a specific person. Finally, a prototype tracklet is extracted for each eBoT, where the occurred occlusions are estimated by relying on a new measure of confidence. We validated our approach over an extensive dataset of egocentric photo-streams and compared it to state of the art methods, demonstrating its effectiveness and robustness.
A semidefinite program for unbalanced multisection in the stochastic block model
Venue: arXiv cs.DS 2016
Year: 2016

We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recovery of the latent communities, up to the information-theoretic limits determined by Abbe and Sandon (2015). Our result extends prior SDP approaches by allowing for many communities of different sizes. By virtue of a semidefinite approach, our algorithms succeed against a semirandom variant of the stochastic block model, guaranteeing a form of robustness and generalization. We further explore how semirandom models can lend insight into both the strengths and limitations of SDPs in this setting.
Design optimisation and resource assessment for tidal-stream renewable energy farms using a new continuous turbine approach
Venue: arXiv cs.CE 2016
Year: 2016

This paper presents a new approach for optimising the design of tidal stream turbine farms. In this approach, the turbine farm is represented by a turbine density function that specifies the number of turbines per unit area and an associated continuous locally-enhanced bottom friction field. The farm design question is formulated as a mathematical optimisation problem constrained by the shallow water equations and solved with efficient, gradient-based optimisation methods. The resulting method is accurate, computationally efficient, allows complex installation constraints, and supports different goal quantities such as to maximise power or profit. The outputs of the optimisation are the optimal number of turbines, their location within the farm, the overall farm profit, the farm's power extraction, and the installation cost. We demonstrate the capabilities of the method on a validated numerical model of the Pentland Firth, Scotland. We optimise the design of four tidal farms simultaneously, as well as individually, and study how farms in close proximity may impact upon one another.