OpenRaiser/Intern-Atlas huggingface dataset:
On the Probe Complexity of Local Computation Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

The Local Computation Algorithms (LCA) model is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using probes: strong probes (SP) specify a vertex $v$ and receive as a reply a list of $v$'s neighbors, and weak probes (WP) specify a vertex $v$ and a port number $i$ and receive as a reply $v$'s $i^{th}$ neighbor. Given a local query (e.g., "is a certain vertex in the vertex cover of the input graph?"), an LCA should compute the corresponding local output (e.g., "yes" or "no") while making only a small number of probes, with the requirement that all local outputs form a single global solution (e.g., a legal vertex cover). We study the probe complexity of LCAs that are required to work on graphs that may have arbitrarily large degrees. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. For weak probes, we focus on the weak coloring problem. Among our results we show a separation between weak 3-coloring and weak 2-coloring for deterministic LCAs: $\log^* n + O(1)$ weak probes suffice for weak 3-coloring, but $Ω\left(\frac{\log n}{\log\log n}\right)$ weak probes are required for weak 2-coloring. For strong probes, we consider randomized LCAs for vertex cover and maximal/maximum matching. Our negative results include showing that there are graphs for which finding a \emph{maximal} matching requires $Ω(\sqrt{n})$ strong probes. On the positive side, we design a randomized LCA that finds a $(1-ε)$ approximation to \emph{maximum} matching in regular graphs, and uses $\frac{1}{ε}^{O\left( \frac{1}{ε^2}\right)}$ probes, independently of the number of vertices and of their degrees.
Supervised Typing of Big Graphs using Semantic Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

We propose a supervised algorithm for generating type embeddings in the same semantic vector space as a given set of entity embeddings. The algorithm is agnostic to the derivation of the underlying entity embeddings. It does not require any manual feature engineering, generalizes well to hundreds of types and achieves near-linear scaling on Big Graphs containing many millions of triples and instances by virtue of an incremental execution. We demonstrate the utility of the embeddings on a type recommendation task, outperforming a non-parametric feature-agnostic baseline while achieving 15x speedup and near-constant memory usage on a full partition of DBpedia. Using state-of-the-art visualization, we illustrate the agreement of our extensionally derived DBpedia type embeddings with the manually curated domain ontology. Finally, we use the embeddings to probabilistically cluster about 4 million DBpedia instances into 415 types in the DBpedia ontology.
Information-theoretic Model Identification and Policy Search using Physics Engines with Application to Robotic Manipulation
Venue: arXiv cs.RO 2017
Year: 2017

We consider the problem of a robot learning the mechanical properties of objects through physical interaction with the object, and introduce a practical, data-efficient approach for identifying the motion models of these objects. The proposed method utilizes a physics engine, where the robot seeks to identify the inertial and friction parameters of the object by simulating its motion under different values of the parameters and identifying those that result in a simulation which matches the observed real motions. The problem is solved in a Bayesian optimization framework. The same framework is used for both identifying the model of an object online and searching for a policy that would minimize a given cost function according to the identified model. Experimental results both in simulation and using a real robot indicate that the proposed method outperforms state-of-the-art model-free reinforcement learning approaches.
Information complexity of the AND function in the two-Party, and multiparty settings
Venue: arXiv cs.CC 2017
Year: 2017

In a recent breakthrough paper [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication, STOC'13] Braverman et al. developed a local characterization for the zero-error information complexity in the two party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function, which was then applied to determine the exact asymptotic of randomized communication complexity of the set disjointness problem. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain distributions. Our proof has new components, and in particular it fixes some minor gaps in the proof of Braverman et al.
Almost-global tracking for a rigid body with internal rotors
Venue: arXiv cs.SY 2017
Year: 2017

Almost-global orientation trajectory tracking for a rigid body with external actuation has been well studied in the literature, and in the geometric setting as well. The tracking control law relies on the fact that a rigid body is a simple mechanical system (SMS) on the $3-$dimensional group of special orthogonal matrices. However, the problem of designing feedback control laws for tracking using internal actuation mechanisms, like rotors or control moment gyros, has received lesser attention from a geometric point of view. An internally actuated rigid body is not a simple mechanical system, and the phase-space here evolves on the level set of a momentum map. In this note, we propose a novel proportional integral derivative (PID) control law for a rigid body with $3$ internal rotors, that achieves tracking of feasible trajectories from almost all initial conditions.
Bidirectional-Convolutional LSTM Based Spectral-Spatial Feature Learning for Hyperspectral Image Classification
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a novel deep learning framework named bidirectional-convolutional long short term memory (Bi-CLSTM) network to automatically learn the spectral-spatial feature from hyperspectral images (HSIs). In the network, the issue of spectral feature extraction is considered as a sequence learning problem, and a recurrent connection operator across the spectral domain is used to address it. Meanwhile, inspired from the widely used convolutional neural network (CNN), a convolution operator across the spatial domain is incorporated into the network to extract the spatial feature. Besides, to sufficiently capture the spectral information, a bidirectional recurrent connection is proposed. In the classification phase, the learned features are concatenated into a vector and fed to a softmax classifier via a fully-connected operator. To validate the effectiveness of the proposed Bi-CLSTM framework, we compare it with several state-of-the-art methods, including the CNN framework, on three widely used HSIs. The obtained results show that Bi-CLSTM can improve the classification performance as compared to other methods.
Changing Fashion Cultures
Venue: arXiv cs.CV 2017
Year: 2017

The paper presents a novel concept that analyzes and visualizes worldwide fashion trends. Our goal is to reveal cutting-edge fashion trends without displaying an ordinary fashion style. To achieve the fashion-based analysis, we created a new fashion culture database (FCDB), which consists of 76 million geo-tagged images in 16 cosmopolitan cities. By grasping a fashion trend of mixed fashion styles,the paper also proposes an unsupervised fashion trend descriptor (FTD) using a fashion descriptor, a codeword vetor, and temporal analysis. To unveil fashion trends in the FCDB, the temporal analysis in FTD effectively emphasizes consecutive features between two different times. In experiments, we clearly show the analysis of fashion trends and fashion-based city similarity. As the result of large-scale data collection and an unsupervised analyzer, the proposed approach achieves world-level fashion visualization in a time series. The code, model, and FCDB will be publicly available after the construction of the project page.
Integral control of port-Hamiltonian systems: non-passive outputs without coordinate transformation
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we present a method for the addition of integral action to non-passive outputs of a class of port-Hamiltonian systems. The proposed integral controller is a dynamic extension, constructed from the open loop system, such that the closed loop preserves the port-Hamiltonian form. It is shown that the controller is able to reject the effects of both matched and unmatched disturbances, preserving the regulation of the non-passive outputs. Previous solutions to this problem have relied on a change of coordinates whereas the presented solution is developed using the original state vector and, therefore, retains its physical interpretation. In addition, the resulting closed loop dynamics have a natural interpretation as a Control by Interconnection scheme.
Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
Venue: arXiv cs.LG 2017
Year: 2017

Recently, research on accelerated stochastic gradient descent methods (e.g., SVRG) has made exciting progress (e.g., linear convergence for strongly convex problems). However, the best-known methods (e.g., Katyusha) requires at least two auxiliary variables and two momentum parameters. In this paper, we propose a fast stochastic variance reduction gradient (FSVRG) method, in which we design a novel update rule with the Nesterov's momentum and incorporate the technique of growing epoch size. FSVRG has only one auxiliary variable and one momentum weight, and thus it is much simpler and has much lower per-iteration complexity. We prove that FSVRG achieves linear convergence for strongly convex problems and the optimal $\mathcal{O}(1/T^2)$ convergence rate for non-strongly convex problems, where $T$ is the number of outer-iterations. We also extend FSVRG to directly solve the problems with non-smooth component functions, such as SVM. Finally, we empirically study the performance of FSVRG for solving various machine learning problems such as logistic regression, ridge regression, Lasso and SVM. Our results show that FSVRG outperforms the state-of-the-art stochastic methods, including Katyusha.
Efficient and Robust Recovery of Sparse Signal and Image Using Generalized Nonconvex Regularization
Venue: arXiv cs.IT 2017
Year: 2017

This work addresses the robust reconstruction problem of a sparse signal from compressed measurements. We propose a robust formulation for sparse reconstruction which employs the $\ell_1$-norm as the loss function for the residual error and utilizes a generalized nonconvex penalty for sparsity inducing. The $\ell_1$-loss is less sensitive to outliers in the measurements than the popular $\ell_2$-loss, while the nonconvex penalty has the capability of ameliorating the bias problem of the popular convex LASSO penalty and thus can yield more accurate recovery. To solve this nonconvex and nonsmooth minimization formulation efficiently, we propose a first-order algorithm based on alternating direction method of multipliers (ADMM). A smoothing strategy on the $\ell_1$-loss function has been used in deriving the new algorithm to make it convergent. Further, a sufficient condition for the convergence of the new algorithm has been provided for generalized nonconvex regularization. In comparison with several state-of-the-art algorithms, the new algorithm showed better performance in numerical experiments in recovering sparse signals and compressible images. The new algorithm scales well for large-scale problems, as often encountered in image processing.
Single Channel Audio Source Separation using Convolutional Denoising Autoencoders
Venue: arXiv cs.SD 2017
Year: 2017

Deep learning techniques have been used recently to tackle the audio source separation problem. In this work, we propose to use deep fully convolutional denoising autoencoders (CDAEs) for monaural audio source separation. We use as many CDAEs as the number of sources to be separated from the mixed signal. Each CDAE is trained to separate one source and treats the other sources as background noise. The main idea is to allow each CDAE to learn suitable spectral-temporal filters and features to its corresponding source. Our experimental results show that CDAEs perform source separation slightly better than the deep feedforward neural networks (FNNs) even with fewer parameters than FNNs.
Cooperative Binning for Semi-deterministic Channels with Non-causal State Information
Venue: arXiv cs.IT 2017
Year: 2017

The capacity of the semi-deterministic relay channel (SD-RC) with non-causal channel state information (CSI) only at the encoder and decoder is characterized. The capacity is achieved by a scheme based on cooperative-bin-forward. This scheme allows cooperation between the transmitter and the relay without the need to decode a part of the message by the relay. The transmission is divided into blocks and each deterministic output of the channel (observed by the relay) is mapped to a bin. The bin index is used by the encoder and the relay to choose the cooperation codeword in the next transmission block. In causal settings the cooperation is independent of the state. In \emph{non-causal} settings dependency between the relay's transmission and the state can increase the transmission rates. The encoder implicitly conveys partial state information to the relay. In particular, it uses the states of the next block and selects a cooperation codeword accordingly and the relay transmission depends on the cooperation codeword and therefore also on the states. We also consider the multiple access channel with partial cribbing as a semi-deterministic channel. The capacity region of this channel with non-causal CSI is achieved by the new scheme. Examining the result in several cases, we introduce a new problem of a point-to-point (PTP) channel where the state is provided to the transmitter by a state encoder. Interestingly, even though the CSI is also available at the receiver, we provide an example which shows that the capacity with non-causal CSI at the state encoder is strictly larger than the capacity with causal CSI.
Extracting a uniform random bit-string over Jacobian of Hyperelliptic curves of Genus $2$
Venue: arXiv cs.CR 2017
Year: 2017

Here, we proposed an improved version of the deterministic random extractors $SEJ$ and $PEJ$ proposed by R. R. Farashahi in \cite{F} in 2009. By using the Mumford's representation of a reduced divisor $D$ of the Jacobian $J(\mathbb{F}_q)$ of a hyperelliptic curve $\mathcal{H}$ of genus $2$ with odd characteristic, we extract a perfectly random bit string of the sum of abscissas of rational points on $\mathcal{H}$ in the support of $D$. By this new approach, we reduce in an elementary way the upper bound of the statistical distance of the deterministic randomness extractors defined over $\mathbb{F}_q$ where $q=p^n$, for some positive integer $n\geq 1$ and $p$ an odd prime.
Understand Your Chains: Towards Performance Profile-based Network Service Management
Venue: arXiv cs.NI 2017
Year: 2017

Allocating resources to virtualized network functions and services to meet service level agreements is a challenging task for NFV management and orchestration systems. This becomes even more challenging when agile development methodologies, like DevOps, are applied. In such scenarios, management and orchestration systems are continuously facing new versions of functions and services which makes it hard to decide how much resources have to be allocated to them to provide the expected service performance. One solution for this problem is to support resource allocation decisions with performance behavior information obtained by profiling techniques applied to such network functions and services. In this position paper, we analyze and discuss the components needed to generate such performance behavior information within the NFV DevOps workflow. We also outline research questions that identify open issues and missing pieces for a fully integrated NFV profiling solution. Further, we introduce a novel profiling mechanism that is able to profile virtualized network functions and entire network service chains under different resource constraints before they are deployed on production infrastructure.
A Time-shared Photonic Reservoir Computer for Big Data Analytics
Venue: arXiv cs.ET 2017
Year: 2017

Information processing has reached the era of big data. Big data challenges are difficult to address with traditional Von Neumann or Turing approach. Hence implementation of new computational techniques is highly essential. Nanophotonics with its remarkable speed and multiplexing capability is a promising candidate for such implementations. This paper proposes a novel photonic computing system made-up of Mach-Zehnder interferometer and an optical fiber spool to emulate a powerful machine learning technique called reservoir computing. The proposed system is also integrated with a time-division-multiplexing circuit to facilitate parallel computation of multiple tasks which is first of its kind. The proposed design performs large-scale tasks like spoken digit recognition, channel equalization, and time-series prediction. Experimental results with standard photonic simulator demonstrate significant performance in terms of speed and accuracy compared to state of the art digital and software implementations.
Improved NN-JPDAF for Joint Multiple Target Tracking and Feature Extraction
Venue: arXiv cs.SY 2017
Year: 2017

Feature aided tracking can often yield improved tracking performance over the standard multiple target tracking (MTT) algorithms with only kinematic measurements. However, in many applications, the feature signal of the targets consists of sparse Fourier-domain signals. It changes quickly and nonlinearly in the time domain, and the feature measurements are corrupted by missed detections and mis-associations. These two factors make it hard to extract the feature information to be used in MTT. In this paper, we develop a feature-aided nearest neighbour joint probabilistic data association filter (NN-JPDAF) for joint MTT and feature extraction in dense target environments. To estimate the rapidly varying feature signal from incomplete and corrupted measurements, we use the atomic norm constraint to formulate the sparsity of feature signal and use the $\ell_1$-norm to formulate the sparsity of the corruption induced by mis-associations. Based on the sparse representation, the feature signal are estimated by solving a semidefinite program (SDP) which is convex. We also provide an iterative method for solving this SDP via the alternating direction method of multipliers (ADMM) where each iteration involves closed-form computation. With the estimated feature signal, re-filtering is performed to estimate the kinematic states of the targets, where the association makes use of both kinematic and feature information. Simulation results are presented to illustrate the performance of the proposed algorithm in a radar application.
Combinatorial metrics: MacWilliams-type identities, isometries and extension property
Venue: arXiv cs.IT 2017
Year: 2017

In this work we characterize the combinatorial metrics admitting a MacWilliams-type identity and describe the group of linear isometries of such metrics. Considering coverings that are not connected, we classify the metrics satisfying the MacWilliams extension property.
Hyper Zagreb Index of Bridge and Chain Grpahs
Venue: arXiv cs.DM 2017
Year: 2017

Let G be a simple connected molecular graph with vertex set $V(G)$ and edge set $E(G)$. One important modification of classical Zagreb index, called hyper Zagreb index $HM(G)$ is defined as the sum of squares of the degree sum of the adjacent vertices, that is, sum of the terms $[{d_G}(u)+{d_G}(v)]^2$ over all the edges of $G$, where ${d_G}(u)$ denote the degree of the vertex $u$ of $G$. In this paper, the hyper Zagreb index of certain bridge and chain graphs are computed and hence using the derived results we compute the hyper Zagreb index of several classes of chemical graphs and nanostructures.
Final-State Constrained Optimal Control via a Projection Operator Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we develop a numerical method to solve nonlinear optimal control problems with final-state constraints. Specifically, we extend the PRojection Operator based Netwon's method for Trajectory Optimization (PRONTO), which was proposed by Hauser for unconstrained optimal control problems. While in the standard method final-state constraints can be only approximately handled by means of a terminal penalty, in this work we propose a methodology to meet the constraints exactly. Moreover, our method guarantees recursive feasibility of the final-state constraint. This is an appealing property especially in realtime applications in which one would like to be able to stop the computation even if the desired tolerance has not been reached, but still satisfy the constraints. Following the same conceptual idea of PRONTO, the proposed strategy is based on two main steps which (differently from the standard scheme) preserve the feasibility of the final-state constraints: (i) solve a quadratic approximation of the nonlinear problem to find a descent direction, and (ii) get a (feasible) trajectory by means of a feedback law (which turns out to be a nonlinear projection operator). To find the (feasible) descent direction we take advantage of final-state constrained Linear Quadratic optimal control methods, while the second step is performed by suitably designing a constrained version of the trajectory tracking projection operator. The effectiveness of the proposed strategy is tested on the optimal state transfer of an inverted pendulum.
A Hybrid Deep Learning Approach for Texture Analysis
Venue: arXiv cs.CV 2017
Year: 2017

Texture classification is a problem that has various applications such as remote sensing and forest species recognition. Solutions tend to be custom fit to the dataset used but fails to generalize. The Convolutional Neural Network (CNN) in combination with Support Vector Machine (SVM) form a robust selection between powerful invariant feature extractor and accurate classifier. The fusion of experts provides stability in classification rates among different datasets.
A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
Venue: arXiv cs.DC 2017
Year: 2017

In this paper we consider a distributed optimization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimization variable. This problem set-up has been shown to appear in many interesting network application scenarios. As main paper contribution, we develop a simple, primal distributed algorithm to solve the optimization problem, based on a randomized descent approach, which works under asynchronous gossip communication. We prove that the proposed asynchronous algorithm is a proper, ad-hoc version of a coordinate descent method and thus converges to a stationary point. To show the effectiveness of the proposed algorithm, we also present numerical simulations on a non-convex quadratic program, which confirm the theoretical results.