OpenRaiser/Intern-Atlas huggingface dataset:
Survey on Combinatorial Register Allocation and Instruction Scheduling
Venue: arXiv cs.PL 2019
Year: 2019

Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to increase instruction-level parallelism) are essential tasks for generating efficient assembly code in a compiler. In the last three decades, combinatorial optimization has emerged as an alternative to traditional, heuristic algorithms for these two tasks. Combinatorial optimization approaches can deliver optimal solutions according to a model, can precisely capture trade-offs between conflicting decisions, and are more flexible at the expense of increased compilation time. This paper provides an exhaustive literature review and a classification of combinatorial optimization approaches to register allocation and instruction scheduling, with a focus on the techniques that are most applied in this context: integer programming, constraint programming, partitioned Boolean quadratic programming, and enumeration. Researchers in compilers and combinatorial optimization can benefit from identifying developments, trends, and challenges in the area; compiler practitioners may discern opportunities and grasp the potential benefit of applying combinatorial optimization.
Salient Object Detection: A Survey
Venue: arXiv cs.CV 2019
Year: 2019

Detecting and segmenting salient objects from natural scenes, often referred to as salient object detection, has attracted great interest in computer vision. While many models have been proposed and several applications have emerged, a deep understanding of achievements and issues remains lacking. We aim to provide a comprehensive review of recent progress in salient object detection and situate this field among other closely related areas such as generic scene segmentation, object proposal generation, and saliency for fixation prediction. Covering 228 publications, we survey i) roots, key concepts, and tasks, ii) core techniques and main modeling trends, and iii) datasets and evaluation metrics for salient object detection. We also discuss open problems such as evaluation metrics and dataset bias in model performance, and suggest future research directions.
Recognition and Complexity of Point Visibility Graphs
Venue: arXiv cs.CG 2019
Year: 2019

A point visibility graph is a graph induced by a set of points in the plane, where every vertex corresponds to a point, and two vertices are adjacent whenever the two corresponding points are visible from each other, that is, the open segment between them does not contain any other point of the set. We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mnëv and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs. Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.
On integer programing with bounded determinants
Venue: arXiv cs.CG 2019
Year: 2019

Let $A$ be an $(m \times n)$ integral matrix, and let $P=\{ x : A x \leq b\}$ be an $n$-dimensional polytope. The width of $P$ is defined as $ w(P)=min\{ x\in \mathbb{Z}^n\setminus\{0\} :\: max_{x \in P} x^\top u - min_{x \in P} x^\top v \}$. Let $Δ(A)$ and $δ(A)$ denote the greatest and the smallest absolute values of a determinant among all $r(A) \times r(A)$ sub-matrices of $A$, where $r(A)$ is the rank of a matrix $A$. We prove that if every $r(A) \times r(A)$ sub-matrix of $A$ has a determinant equal to $\pm Δ(A)$ or $0$ and $w(P)\ge (Δ(A)-1)(n+1)$, then $P$ contains $n$ affine independent integer points. Also we have similar results for the case of \emph{$k$-modular} matrices. The matrix $A$ is called \emph{totally $k$-modular} if every square sub-matrix of $A$ has a determinant in the set $\{0,\, \pm k^r :\: r \in \mathbb{N} \}$. When $P$ is a simplex and $w(P)\ge δ(A)-1$, we describe a polynomial time algorithm for finding an integer point in $P$. Finally we show that if $A$ is \emph{almost unimodular}, then integer program $\max \{c^\top x :\: x \in P \cap \mathbb{Z}^n \}$ can be solved in polynomial time. The matrix $A$ is called \emph{almost unimodular} if $Δ(A) \leq 2$ and any $(r(A)-1)\times(r(A)-1)$ sub-matrix has a determinant from the set $\{0,\pm 1\}$.
Approximate Euclidean shortest paths in polygonal domains
Venue: arXiv cs.CG 2019
Year: 2019

Given a set $\mathcal{P}$ of $h$ pairwise disjoint simple polygonal obstacles in $\mathbb{R}^2$ defined with $n$ vertices, we compute a sketch $Ω$ of $\mathcal{P}$ whose size is independent of $n$, depending only on $h$ and the input parameter $ε$. We utilize $Ω$ to compute a $(1+ε)$-approximate geodesic shortest path between the two given points in $O(n + h((\lg{n}) + (\lg{h})^{1+δ} + (\frac{1}ε\lg{\frac{h}ε})))$ time. Here, $ε$ is a user parameter, and $δ$ is a small positive constant (resulting from the time for triangulating the free space of $\cal P$ using the algorithm in \cite{journals/ijcga/Bar-YehudaC94}). Moreover, we devise a $(2+ε)$-approximation algorithm to answer two-point Euclidean distance queries for the case of convex polygonal obstacles.
Hodge Laplacians on graphs
Venue: arXiv cs.IT 2019
Year: 2019

This is an elementary introduction to the Hodge Laplacian on a graph, a higher-order generalization of the graph Laplacian. We will discuss basic properties including cohomology and Hodge theory. The main feature of our approach is simplicity, requiring only knowledge of linear algebra and graph theory. We have also isolated the algebra from the topology to show that a large part of cohomology and Hodge theory is nothing more than the linear algebra of matrices satisfying $AB = 0$. For the remaining topological aspect, we cast our discussions entirely in terms of graphs as opposed to less-familiar topological objects like simplicial complexes.
Syntax Evolution: Problems and Recursion
Venue: arXiv cs.CL 2019
Year: 2019

To investigate the evolution of syntax, we need to ascertain the evolutionary rôle of syntax and, before that, the very nature of syntax. Here, we will assume that syntax is computing. And then, since we are computationally Turing complete, we meet an evolutionary anomaly, the anomaly of sytax: we are syntactically too competent for syntax. Assuming that problem solving is computing, and realizing that the evolutionary advantage of Turing completeness is full problem solving and not syntactic proficiency, we explain the anomaly of syntax by postulating that syntax and problem solving co-evolved in humans towards Turing completeness. Examining the requirements that full problem solving impose on language, we find firstly that semantics is not sufficient and that syntax is necessary to represent problems. Our final conclusion is that full problem solving requires a functional semantics on an infinite tree-structured syntax. Besides these results, the introduction of Turing completeness and problem solving to explain the evolution of syntax should help us to fit the evolution of language within the evolution of cognition, giving us some new clues to understand the elusive relation between language and thinking.
Dual Principal Component Pursuit
Venue: arXiv cs.CV 2019
Year: 2019

We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex $\ell_1$ minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications.
Stabilizing the unstable output of persistent homology computations
Venue: arXiv cs.CG 2019
Year: 2019

We propose a general technique for extracting a larger set of stable information from persistent homology computations than is currently done. The persistent homology algorithm is usually viewed as a procedure which starts with a filtered complex and ends with a persistence diagram. This procedure is stable (at least to certain types of perturbations of the input). This justifies the use of the diagram as a signature of the input, and the use of features derived from it in statistics and machine learning. However, these computations also produce other information of great interest to practitioners that is unfortunately unstable. For example, each point in the diagram corresponds to a simplex whose addition in the filtration results in the birth of the corresponding persistent homology class, but this correspondence is unstable. In addition, the persistence diagram is not stable with respect to other procedures that are employed in practice, such as thresholding a point cloud by density. We recast these problems as real-valued functions which are discontinuous but measurable, and then observe that convolving such a function with a suitable function produces a Lipschitz function. The resulting stable function can be estimated by perturbing the input and averaging the output. We illustrate this approach with a number of examples, including a stable localization of a persistent homology generator from brain imaging data.
Random Sampling with Removal
Venue: arXiv cs.CG 2019
Year: 2019

We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator spaces; and a setting we introduce, consistent spaces. Such algorithms typically involve a step of finding the optimal solution for a random sample of the constraints. They exploit the condition that, in finite dimension $δ$, this sample optimum violates a provably small expected fraction of the non-sampled constraints, with the fraction decreasing in the sample size~$r$. We extend such algorithms by considering the technique of removal, where a fixed number $k$ of constraints are removed from the sample according to a fixed rule, with the goal of improving the solution quality. This may have the effect of increasing the number of violated non-sampled constraints. We study this increase, and bound it in a variety of general settings. This work is motivated by, and extends, results on removal as proposed for chance-constrained optimization. For many relevant values of $r$, $δ$, and $k$, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of $k$ constraints. For a large range of values of $k$, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases, and not in the generality we consider. Moreover, we show that our results extend from finite to infinite spaces, for chance-constrained optimization.
Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane
Venue: arXiv cs.DS 2019
Year: 2019

Given a set $P$ of $n$ points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the $l_1$ distance. In this paper, a fixed-parameter algorithm for the Rectilinear TSP is presented and relies on techniques for solving TSP on bounded-treewidth graphs. It proves that the problem can be solved in $O\left(nh7^h\right)$ where $h \leq n$ denotes the number of horizontal lines containing the points of $P$. The same technique can be directly applied to the problem of finding a shortest rectilinear Steiner tree that interconnects the points of $P$ providing a $O\left(nh5^h\right)$ time complexity. Both bounds improve over the best time bounds known for these problems.
Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach
Venue: arXiv cs.IT 2019
Year: 2019

A $q$-ary $(n,k,r)$ locally repairable code (LRC) is an $[n,k,d]$ linear code over $\mathbb{F}_q$ such that every code symbol can be recovered by accessing at most $r$ other code symbols. The well-known Singleton-like bound says that $d \le n-k-\lceil k/r\rceil +2$ and an LRC is said to be optimal if it attains this bound. In this paper, we study the bounds and constructions of LRCs from the view of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed. Several useful structural properties on $q$-ary optimal LRCs are obtained. We derive an upper bound on the minimum distance of $q$-ary optimal $(n,k,r)$-LRCs in terms of the field size $q$. Then, we focus on constructions of optimal LRCs over binary field. It is proved that there are only 5 classes of possible parameters with which optimal binary $(n,k,r)$-LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these 5 classes of possible optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes.
EEG-informed attended speaker extraction from recorded speech mixtures with application in neuro-steered hearing prostheses
Venue: arXiv cs.SD 2019
Year: 2019

OBJECTIVE: We aim to extract and denoise the attended speaker in a noisy, two-speaker acoustic scenario, relying on microphone array recordings from a binaural hearing aid, which are complemented with electroencephalography (EEG) recordings to infer the speaker of interest. METHODS: In this study, we propose a modular processing flow that first extracts the two speech envelopes from the microphone recordings, then selects the attended speech envelope based on the EEG, and finally uses this envelope to inform a multi-channel speech separation and denoising algorithm. RESULTS: Strong suppression of interfering (unattended) speech and background noise is achieved, while the attended speech is preserved. Furthermore, EEG-based auditory attention detection (AAD) is shown to be robust to the use of noisy speech signals. CONCLUSIONS: Our results show that AAD-based speaker extraction from microphone array recordings is feasible and robust, even in noisy acoustic environments, and without access to the clean speech signals to perform EEG-based AAD. SIGNIFICANCE: Current research on AAD always assumes the availability of the clean speech signals, which limits the applicability in real settings. We have extended this research to detect the attended speaker even when only microphone recordings with noisy speech mixtures are available. This is an enabling ingredient for new brain-computer interfaces and effective filtering schemes in neuro-steered hearing prostheses. Here, we provide a first proof of concept for EEG-informed attended speaker extraction and denoising.
Coordination Event Detection and Initiator Identification in Time Series Data
Venue: arXiv cs.SI 2019
Year: 2019

Behavior initiation is a form of leadership and is an important aspect of social organization that affects the processes of group formation, dynamics, and decision-making in human societies and other social animal species. In this work, we formalize the "Coordination Initiator Inference Problem" and propose a simple yet powerful framework for extracting periods of coordinated activity and determining individuals who initiated this coordination, based solely on the activity of individuals within a group during those periods. The proposed approach, given arbitrary individual time series, automatically (1) identifies times of coordinated group activity, (2) determines the identities of initiators of those activities, and (3) classifies the likely mechanism by which the group coordination occurred, all of which are novel computational tasks. We demonstrate our framework on both simulated and real-world data: trajectories tracking of animals as well as stock market data. Our method is competitive with existing global leadership inference methods but provides the first approaches for local leadership and coordination mechanism classification. Our results are consistent with ground-truthed biological data and the framework finds many known events in financial data which are not otherwise reflected in the aggregate NASDAQ index. Our method is easily generalizable to any coordinated time-series data from interacting entities.
U-CATCH: Using Color ATtribute of image patCHes in binary descriptors
Venue: arXiv cs.CV 2019
Year: 2019

In this study, we propose a simple yet very effective method for extracting color information through binary feature description framework. Our method expands the dimension of binary comparisons into RGB and YCbCr spaces, showing more than 100% matching improve ment compared to non-color binary descriptors for a wide range of hard-to-match cases. The proposed method is general and can be applied to any binary descriptor to make it color sensitive. It is faster than classical binary descriptors for RGB sampling due to the abandonment of grayscale conversion and has almost identical complexity (insignificant compared to smoothing operation) for YCbCr sampling.
Pre-Expansivity in Cellular Automata
Venue: arXiv cs.DM 2019
Year: 2019

We introduce the property of pre-expansivity for cellular automata (CA): it is the property of being expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between expansivity and pre-injectivity, two important notions of CA theory. We show that there exist one-dimensional positively pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We show however that no bi-dimensional CA which is linear over an Abelian group can be pre-expansive. We also consider the finer notion of k-expansivity (expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.
Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
Venue: arXiv cs.LG 2019
Year: 2019

We present new excess risk bounds for general unbounded loss functions including log loss and squared loss, where the distribution of the losses may be heavy-tailed. The bounds hold for general estimators, but they are optimized when applied to $η$-generalized Bayesian, MDL, and empirical risk minimization estimators. In the case of log loss, the bounds imply convergence rates for generalized Bayesian inference under misspecification in terms of a generalization of the Hellinger metric as long as the learning rate $η$ is set correctly. For general loss functions, our bounds rely on two separate conditions: the $v$-GRIP (generalized reversed information projection) conditions, which control the lower tail of the excess loss; and the newly introduced witness condition, which controls the upper tail. The parameter $v$ in the $v$-GRIP conditions determines the achievable rate and is akin to the exponent in the Tsybakov margin condition and the Bernstein condition for bounded losses, which the $v$-GRIP conditions generalize; favorable $v$ in combination with small model complexity leads to $\tilde{O}(1/n)$ rates. The witness condition allows us to connect the excess risk to an "annealed" version thereof, by which we generalize several previous results connecting Hellinger and Rényi divergence to KL divergence.
Parallel Wavelet Schemes for Images
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we introduce several new schemes for calculation of discrete wavelet transforms of images. These schemes reduce the number of steps and, as a consequence, allow to reduce the number of synchronizations on parallel architectures. As an additional useful property, the proposed schemes can reduce also the number of arithmetic operations. The schemes are primarily demonstrated on CDF 5/3 and CDF 9/7 wavelets employed in JPEG 2000 image compression standard. However, the presented method is general, and it can be applied on any wavelet transform. As a result, our scheme requires only two memory barriers for 2-D CDF 5/3 transform compared to four barriers in the original separable form or three barriers in the non-separable scheme recently published. Our reasoning is supported by exhaustive experiments on high-end graphics cards.
Fog-Aided Wireless Networks for Content Delivery: Fundamental Latency Trade-Offs
Venue: arXiv cs.IT 2019
Year: 2019

A fog-aided wireless network architecture is studied in which edge-nodes (ENs), such as base stations, are connected to a cloud processor via dedicated fronthaul links, while also being endowed with caches. Cloud processing enables the centralized implementation of cooperative transmission strategies at the ENs, albeit at the cost of an increased latency due to fronthaul transfer. In contrast, the proactive caching of popular content at the ENs allows for the low-latency delivery of the cached files, but with generally limited opportunities for cooperative transmission among the ENs. The interplay between cloud processing and edge caching is addressed from an information-theoretic viewpoint by investigating the fundamental limits of a high Signal-to-Noise-Ratio (SNR) metric, termed normalized delivery time (NDT), which captures the worst-case coding latency for delivering any requested content to the users. The NDT is defined under the assumptions of either serial or pipelined fronthaul-edge transmission, and is studied as a function of fronthaul and cache capacity constraints. Placement and delivery strategies across both fronthaul and wireless, or edge, segments are proposed with the aim of minimizing the NDT. Information-theoretic lower bounds on the NDT are also derived. Achievability arguments and lower bounds are leveraged to characterize the minimal NDT in a number of important special cases, including systems with no caching capabilities, as well as to prove that the proposed schemes achieve optimality within a constant multiplicative factor of 2 for all values of the problem parameters.