OpenRaiser/Intern-Atlas huggingface dataset:
Iterative Hard Thresholding for Weighted Sparse Approximation
Venue: arXiv cs.IT 2015
Year: 2015

Recent work by Rauhut and Ward developed a notion of weighted sparsity and a corresponding notion of Restricted Isometry Property for the space of weighted sparse signals. Using these notions, we pose a best weighted sparse approximation problem, i.e. we seek structured sparse solutions to underdetermined systems of linear equations. Many computationally efficient greedy algorithms have been developed to solve the problem of best $s$-sparse approximation. The design of all of these algorithms employ a similar template of exploiting the RIP and computing projections onto the space of sparse vectors. We present an extension of the Iterative Hard Thresholding (IHT) algorithm to solve the weighted sparse approximation problem. This IHT extension employs a weighted analogue of the template employed by all greedy sparse approximation algorithms. Theoretical guarantees are presented and much of the original analysis remains unchanged and extends quite naturally. However, not all the theoretical analysis extends. To this end, we identify and discuss the barrier to extension. Much like IHT, our IHT extension requires computing a projection onto a non-convex space. However unlike IHT and other greedy methods which deal with the classical notion of sparsity, no simple method is known for computing projections onto these weighted sparse spaces. Therefore we employ a surrogate for the projection and analyze its empirical performance.
Connectedness of graphs and its application to connected matroids through covering-based rough sets
Venue: arXiv cs.AI 2015
Year: 2015

Graph theoretical ideas are highly utilized by computer science fields especially data mining. In this field, a data structure can be designed in the form of tree. Covering is a widely used form of data representation in data mining and covering-based rough sets provide a systematic approach to this type of representation. In this paper, we study the connectedness of graphs through covering-based rough sets and apply it to connected matroids. First, we present an approach to inducing a covering by a graph, and then study the connectedness of the graph from the viewpoint of the covering approximation operators. Second, we construct a graph from a matroid, and find the matroid and the graph have the same connectedness, which makes us to use covering-based rough sets to study connected matroids. In summary, this paper provides a new approach to studying graph theory and matroid theory.
A Class of Five-weight Cyclic Codes and Their Weight Distribution
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a family of five-weight reducible cyclic codes is presented. Furthermore, the weight distribution of these cyclic codes is determined, which follows from the determination of value distributions of certain exponential sums.
Learning Generative Models with Visual Attention
Venue: arXiv cs.CV 2015
Year: 2015

Attention has long been proposed by psychologists as important for effectively dealing with the enormous sensory stimulus available in the neocortex. Inspired by the visual attention models in computational neuroscience and the need of object-centric data for generative models, we describe for generative learning framework using attentional mechanisms. Attentional mechanisms can propagate signals from region of interest in a scene to an aligned canonical representation, where generative modeling takes place. By ignoring background clutter, generative models can concentrate their resources on the object of interest. Our model is a proper graphical model where the 2D Similarity transformation is a part of the top-down process. A ConvNet is employed to provide good initializations during posterior inference which is based on Hamiltonian Monte Carlo. Upon learning images of faces, our model can robustly attend to face regions of novel test subjects. More importantly, our model can learn generative models of new faces from a novel dataset of large images where the face locations are not known.
Hygro-thermo-mechanical analysis of spalling in concrete walls at high temperatures as a moving boundary problem
Venue: arXiv cs.CE 2015
Year: 2015

A mathematical model allowing coupled hygro-thermo-mechanical analysis of spalling in concrete walls at high temperatures by means of the moving boundary problem is presented. A simplified mechanical approach to account for effects of thermal stresses and pore pressure build-up on spalling is incorporated into the model. The numerical algorithm based on finite element discretization in space and the semi-implicit method for discretization in time is presented. The validity of the developed model is carefully examined by a comparison between experimental tests performed by Kalifa et al. (2000) and Mindeguia (2009) on concrete prismatic specimens under unidirectional heating of temperature of 600 $°$C and ISO 834 fire curve and the results obtained from the numerical model.
Across neighbourhood search for numerical optimization
Venue: arXiv cs.NE 2015
Year: 2015

Population-based search algorithms (PBSAs), including swarm intelligence algorithms (SIAs) and evolutionary algorithms (EAs), are competitive alternatives for solving complex optimization problems and they have been widely applied to real-world optimization problems in different fields. In this study, a novel population-based across neighbourhood search (ANS) is proposed for numerical optimization. ANS is motivated by two straightforward assumptions and three important issues raised in improving and designing efficient PBSAs. In ANS, a group of individuals collaboratively search the solution space for an optimal solution of the optimization problem considered. A collection of superior solutions found by individuals so far is maintained and updated dynamically. At each generation, an individual directly searches across the neighbourhoods of multiple superior solutions with the guidance of a Gaussian distribution. This search manner is referred to as across neighbourhood search. The characteristics of ANS are discussed and the concept comparisons with other PBSAs are given. The principle behind ANS is simple. Moreover, ANS is easy for implementation and application with three parameters being required to tune. Extensive experiments on 18 benchmark optimization functions of different types show that ANS has well balanced exploration and exploitation capabilities and performs competitively compared with many efficient PBSAs (Related Matlab codes used in the experiments are available from http://guohuawunudt.gotoip2.com/publications.html).
Network Synchronization with Nonlinear Dynamics and Switching Interactions
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the synchronization problem for networks of coupled nonlinear dynamical systems under switching communication topologies. Two types of nonlinear agent dynamics are considered. The first one is non-expansive dynamics (stable dynamics with a convex Lyapunov function $φ(\cdot)$) and the second one is dynamics that satisfies a global Lipschitz condition. For the non-expansive case, we show that various forms of joint connectivity for communication graphs are sufficient for networks to achieve global asymptotic $φ$-synchronization. We also show that $φ$-synchronization leads to state synchronization provided that certain additional conditions are satisfied. For the globally Lipschitz case, unlike the non-expansive case, joint connectivity alone is not sufficient for achieving synchronization. A sufficient condition for reaching global exponential synchronization is established in terms of the relationship between the global Lipschitz constant and the network parameters. We also extend the results to leader-follower networks.
Space-efficient Verifiable Secret Sharing Using Polynomial Interpolation
Venue: arXiv cs.CR 2015
Year: 2015

Preserving data confidentiality in clouds is a key issue. Secret Sharing, a cryptographic primitive for the distribution of a secret among a group of $n$ participants designed so that only subsets of shareholders of cardinality $0 < t \leq n$ are allowed to reconstruct the secret by pooling their shares, can help mitigating and minimizing the problem. A desirable feature of Secret Sharing schemes is cheater detection, i.e. the ability to detect one or more malicious shareholders trying to reconstruct the secret by obtaining legal shares from the other shareholders while providing them with fake shares. Verifiable Secret Sharing schemes solve this problem by allowing shareholders verifying the others' shares. We present new verification algorithms providing arbitrary secret sharing schemes with cheater detection capabilities, and prove their space efficiency with regard to other schemes appeared in the literature. We also introduce, in one of our schemes, the Exponentiating Polynomial Root Problem (EPRP), which is believed to be NP-Intermediate and therefore difficult.
Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
Venue: arXiv cs.IT 2015
Year: 2015

We propose extended coherence-based conditions for exact sparse support recovery using orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). Unlike standard uniform guarantees, we embed some information about the decay of the sparse vector coefficients in our conditions. As a result, the standard condition $μ<1/(2k-1)$ (where $μ$ denotes the mutual coherence and $k$ the sparsity level) can be weakened as soon as the non-zero coefficients obey some decay, both in the noiseless and the bounded-noise scenarios. Furthermore, the resulting condition is approaching $μ<1/k$ for strongly decaying sparse signals. Finally, in the noiseless setting, we prove that the proposed conditions, in particular the bound $μ<1/k$, are the tightest achievable guarantees based on mutual coherence.
Extrinsic Methods for Coding and Dictionary Learning on Grassmann Manifolds
Venue: arXiv cs.LG 2015
Year: 2015

Sparsity-based representations have recently led to notable results in various visual recognition tasks. In a separate line of research, Riemannian manifolds have been shown useful for dealing with features and models that do not lie in Euclidean spaces. With the aim of building a bridge between the two realms, we address the problem of sparse coding and dictionary learning over the space of linear subspaces, which form Riemannian structures known as Grassmann manifolds. To this end, we propose to embed Grassmann manifolds into the space of symmetric matrices by an isometric mapping. This in turn enables us to extend two sparse coding schemes to Grassmann manifolds. Furthermore, we propose closed-form solutions for learning a Grassmann dictionary, atom by atom. Lastly, to handle non-linearity in data, we extend the proposed Grassmann sparse coding and dictionary learning algorithms through embedding into Hilbert spaces. Experiments on several classification tasks (gender recognition, gesture classification, scene analysis, face recognition, action recognition and dynamic texture classification) show that the proposed approaches achieve considerable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as kernelized Affine Hull Method and graph-embedding Grassmann discriminant analysis.
A Fixed Point Theorem for Non-Monotonic Functions
Venue: arXiv cs.LO 2015
Year: 2015

We present a fixed point theorem for a class of (potentially) non-monotonic functions over specially structured complete lattices. The theorem has as a special case the Knaster-Tarski fixed point theorem when restricted to the case of monotonic functions and Kleene's theorem when the functions are additionally continuous. From the practical side, the theorem has direct applications in the semantics of negation in logic programming. In particular, it leads to a more direct and elegant proof of the least fixed point result of [Rondogiannis and W.W.Wadge, ACM TOCL 6(2): 441-467 (2005)]. Moreover, the theorem appears to have potential for possible applications outside the logic programming domain.
A Representation Theorem for Second-Order Functionals
Venue: arXiv cs.PL 2015
Year: 2015

Representation theorems relate seemingly complex objects to concrete, more tractable ones. In this paper, we take advantage of the abstraction power of category theory and provide a general representation theorem for a wide class of second-order functionals which are polymorphic over a class of functors. Types polymorphic over a class of functors are easily representable in languages such as Haskell, but are difficult to analyse and reason about. The concrete representation provided by the theorem is easier to analyse, but it might not be as convenient to implement. Therefore, depending on the task at hand, the change of representation may prove valuable in one direction or the other. We showcase the usefulness of the representation theorem with a range of examples. Concretely, we show how the representation theorem can be used to show that traversable functors are finitary containers, how parameterised coalgebras relate to very well-behaved lenses, and how algebraic effects might be implemented in a functional language.
Dining Cryptographers with 0.924 Verifiable Collision Resolution
Venue: arXiv cs.CR 2015
Year: 2015

The dining cryptographers protocol implements a multiple access channel in which senders and recipients are anonymous. A problem is that a malicious participant can disrupt communication by deliberately creating collisions. We propose a computationally secure dining cryptographers protocol with collision resolution that achieves a maximum stable throughput of 0.924 messages per round and which allows to easily detect disruptors.
Dining Cryptographers are Practical
Venue: arXiv cs.CR 2015
Year: 2015

The dining cryptographers protocol provides information-theoretically secure sender and recipient untraceability. However, the protocol is considered to be impractical because a malicious participant may disrupt the communication. We propose an implementation which provides information-theoretical security for senders and recipients, and in which a disruptor with limited computational capabilities can easily be detected.
Tree 3-spanners of diameter at most 5
Venue: arXiv cs.DM 2015
Year: 2015

Tree spanners approximate distances within graphs; a subtree of a graph is a tree $t$-spanner of the graph if and only if for every pair of vertices their distance in the subtree is at most $t$ times their distance in the graph. When a graph contains a subtree of diameter at most $t$, then trivially admits a tree $t$-spanner. Now, determining whether a graph admits a tree $t$-spanner of diameter at most $t+1$ is an NP complete problem, when $t\geq 4$, and it is tractable, when $t\leq 3$. Although it is not known whether it is tractable to decide graphs that admit a tree 3-spanner of any diameter, an efficient algorithm to determine graphs that admit a tree 3-spanner of diameter at most 5 is presented. Moreover, it is proved that if a graph of diameter at most 3 admits a tee 3-spanner, then it admits a tree 3-spanner of diameter at most 5. Hence, this algorithm decides tree 3-spanner admissibility of diameter at most 3 graphs.
Minority Becomes Majority in Social Networks
Venue: arXiv cs.GT 2015
Year: 2015

It is often observed that agents tend to imitate the behavior of their neighbors in a social network. This imitating behavior might lead to the strategic decision of adopting a public behavior that differs from what the agent believes is the right one and this can subvert the behavior of the population as a whole. In this paper, we consider the case in which agents express preferences over two alternatives and model social pressure with the majority dynamics: at each step an agent is selected and its preference is replaced by the majority of the preferences of her neighbors. In case of a tie, the agent does not change her current preference. A profile of the agents' preferences is stable if the preference of each agent coincides with the preference of at least half of the neighbors (thus, the system is in equilibrium). We ask whether there are network topologies that are robust to social pressure. That is, we ask if there are graphs in which the majority of preferences in an initial profile always coincides with the majority of the preference in all stable profiles reachable from that profile. We completely characterize the graphs with this robustness property by showing that this is possible only if the graph has no edge or is a clique or very close to a clique. In other words, except for this handful of graphs, every graph admits at least one initial profile of preferences in which the majority dynamics can subvert the initial majority. We also show that deciding whether a graph admits a minority that becomes majority is NP-hard when the minority size is at most 1/4-th of the social network size.
Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-$1$ Updates
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we provide local and global convergence guarantees for recovering CP (Candecomp/Parafac) tensor decomposition. The main step of the proposed algorithm is a simple alternating rank-$1$ update which is the alternating version of the tensor power iteration adapted for asymmetric tensors. Local convergence guarantees are established for third order tensors of rank $k$ in $d$ dimensions, when $k=o \bigl( d^{1.5} \bigr)$ and the tensor components are incoherent. Thus, we can recover overcomplete tensor decomposition. We also strengthen the results to global convergence guarantees under stricter rank condition $k \le βd$ (for arbitrary constant $β> 1$) through a simple initialization procedure where the algorithm is initialized by top singular vectors of random tensor slices. Furthermore, the approximate local convergence guarantees for $p$-th order tensors are also provided under rank condition $k=o \bigl( d^{p/2} \bigr)$. The guarantees also include tight perturbation analysis given noisy tensor.
A Technique for Deriving Equational Conditions on the Denavit-Hartenberg Parameters of 6R Linkages that are Necessary for Movability
Venue: arXiv cs.RO 2015
Year: 2015

A closed 6R linkage is generically rigid. Special cases may be mobile. Many families of mobile 6R linkages have been characterised in terms of the invariant Denavit-Hartenberg parameters of the linkage. In other words, many sufficient conditions for mobility are known. In this paper we give, for the first time, equational conditions on the invariant Denavit-Hartenberg parameters that are necessary for mobility. The method is based on the theory of bonds. We illustrate the method by deriving the equational conditions for various well-known linkages (Bricard's line symmetric linkage, Hooke's linkage, Dietmaier's linkage, and recent a generalization of Bricard's orthogonal linkage), starting from their bond diagrams; and by deriving the equations for another bond diagram, thereby discovering a new mobile 6R linkage.
Discovering the Network Backbone from Traffic Activity Data
Venue: arXiv cs.SI 2015
Year: 2015

We introduce a new computational problem, the BackboneDiscovery problem, which encapsulates both functional and structural aspects of network analysis. While the topology of a typical road network has been available for a long time (e.g., through maps), it is only recently that fine-granularity functional (activity and usage) information about the network (like source-destination traffic information) is being collected and is readily available. The combination of functional and structural information provides an efficient way to explore and understand usage patterns of networks and aid in design and decision making. We propose efficient algorithms for the BackboneDiscovery problem including a novel use of edge centrality. We observe that for many real world networks, our algorithm produces a backbone with a small subset of the edges that support a large percentage of the network activity.
Resourceful Contextual Bandits
Venue: arXiv cs.LG 2015
Year: 2015

We study contextual bandits with ancillary constraints on resources, which are common in real-world applications such as choosing ads or dynamic pricing of items. We design the first algorithm for solving these problems that handles constrained resources other than time, and improves over a trivial reduction to the non-contextual case. We consider very general settings for both contextual bandits (arbitrary policy sets, e.g. Dudik et al. (UAI'11)) and bandits with resource constraints (bandits with knapsacks, Badanidiyuru et al. (FOCS'13)), and prove a regret guarantee with near-optimal statistical properties.
An Incidence Geometry approach to Dictionary Learning
Venue: arXiv cs.LG 2015
Year: 2015

We study the Dictionary Learning (aka Sparse Coding) problem of obtaining a sparse representation of data points, by learning \emph{dictionary vectors} upon which the data points can be written as sparse linear combinations. We view this problem from a geometry perspective as the spanning set of a subspace arrangement, and focus on understanding the case when the underlying hypergraph of the subspace arrangement is specified. For this Fitted Dictionary Learning problem, we completely characterize the combinatorics of the associated subspace arrangements (i.e.\ their underlying hypergraphs). Specifically, a combinatorial rigidity-type theorem is proven for a type of geometric incidence system. The theorem characterizes the hypergraphs of subspace arrangements that generically yield (a) at least one dictionary (b) a locally unique dictionary (i.e.\ at most a finite number of isolated dictionaries) of the specified size. We are unaware of prior application of combinatorial rigidity techniques in the setting of Dictionary Learning, or even in machine learning. We also provide a systematic classification of problems related to Dictionary Learning together with various algorithms, their assumptions and performance.
Multi-Objective Resource Allocation for Secure Communication in Cognitive Radio Networks with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study resource allocation for multiuser multiple-input single-output secondary communication systems with multiple system design objectives. We consider cognitive radio networks where the secondary receivers are able to harvest energy from the radio frequency when they are idle. The secondary system provides simultaneous wireless power and secure information transfer to the secondary receivers. We propose a multi-objective optimization framework for the design of a Pareto optimal resource allocation algorithm based on the weighted Tchebycheff approach. In particular, the algorithm design incorporates three important system objectives: total transmit power minimization, energy harvesting efficiency maximization, and interference power leakage-to-transmit power ratio minimization. The proposed framework takes into account a quality of service requirement regarding communication secrecy in the secondary system and the imperfection of the channel state information of potential eavesdroppers (idle secondary receivers and primary receivers) at the secondary transmitter. The adopted multi-objective optimization problem is non-convex and is recast as a convex optimization problem via semidefinite programming (SDP) relaxation. It is shown that the global optimal solution of the original problem can be constructed by exploiting both the primal and the dual optimal solutions of the SDP relaxed problem. Besides, two suboptimal resource allocation schemes for the case when the solution of the dual problem is unavailable for constructing the optimal solution are proposed. Numerical results not only demonstrate the close-to-optimal performance of the proposed suboptimal schemes, but also unveil an interesting trade-off between the considered conflicting system design objectives.