OpenRaiser/Intern-Atlas huggingface dataset:
The Restricted Isometry Property of Block Diagonal Matrices for Group-Sparse Signal Recovery
Venue: arXiv cs.IT 2022
Year: 2022

Group-sparsity is a common low-complexity signal model with widespread application across various domains of science and engineering. The recovery of such signal ensembles from compressive measurements has been extensively studied in the literature under the assumption that measurement operators are modeled as densely populated random matrices. In this paper, we turn our attention to an acquisition model intended to ease the energy consumption of sensing devices by splitting the measurements up into distinct signal blocks. More precisely, we present uniform guarantees for group-sparse signal recovery in the scenario where a number of sensors obtain independent partial signal observations modeled by block diagonal measurement matrices. We establish a group-sparse variant of the classical restricted isometry property for block diagonal sensing matrices acting on group-sparse vectors, and provide conditions under which subgaussian block diagonal random matrices satisfy this group-RIP with high probability. Two different scenarios are considered in particular. In the first scenario, we assume that each sensor is equipped with an independently drawn measurement matrix. We later lift this requirement by considering measurement matrices with constant block diagonal entries. In other words, every sensor is equipped with a copy of the same prototype matrix. The problem of establishing the group-RIP is cast into a form in which one needs to establish the concentration behavior of the suprema of chaos processes which involves estimating Talagrand's $γ_2$ functional. As a side effect of the proof, we present an extension to Maurey's empirical method to provide new bounds on the covering number of sets consisting of finite convex combinations of possibly infinite sets.
Canonisation and Definability for Graphs of Bounded Rank Width
Venue: arXiv cs.DS 2022
Year: 2022

We prove that the combinatorial Weisfeiler-Leman algorithm of dimension $(3k+4)$ is a complete isomorphism test for the class of all graphs of rank width at most $k$. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width $k$ is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time $n^{f(k)}$ for a non-elementary function $f$. Our result yields an isomorphism test for graphs of rank width $k$ running in time $n^{O(k)}$. Another consequence of our result is the first polynomial time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width.
Quantum Sparse Support Vector Machines
Venue: arXiv cs.LG 2022
Year: 2022

We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the $L_1$ norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fraction of the input features in making decisions, and is especially useful when the total number of features, $p$, approaches or exceeds the number of training samples, $m$. We prove a $Ω(m)$ worst-case lower bound for computational complexity of any quantum training algorithm relying on black-box access to training samples; quantum sparse SVM has at least linear worst-case complexity. However, we prove that there are realistic scenarios in which a sparse linear classifier is expected to have high accuracy, and can be trained in sublinear time in terms of both the number of training samples and the number of features.
Real-time malware process detection and automated process killing
Venue: arXiv cs.CR 2022
Year: 2022

Perimeter-based detection is no longer sufficient for mitigating the threat posed by malicious software. This is evident as antivirus (AV) products are replaced by endpoint detection and response (EDR) products, the latter allowing visibility into live machine activity rather than relying on the AV to filter out malicious artefacts. This paper argues that detecting malware in real-time on an endpoint necessitates an automated response due to the rapid and destructive nature of some malware. The proposed model uses statistical filtering on top of a machine learning dynamic behavioural malware detection model in order to detect individual malicious processes on the fly and kill those which are deemed malicious. In an experiment to measure the tangible impact of this system, we find that fast-acting ransomware is prevented from corrupting 92% of files with a false positive rate of 14%. Whilst the false-positive rate currently remains too high to adopt this approach as-is, these initial results demonstrate the need for a detection model which is able to act within seconds of the malware execution beginning; a timescale that has not been addressed by previous work.
Equivalent Polyadic Decompositions of Matrix Multiplication Tensors
Venue: arXiv cs.CC 2022
Year: 2022

Invariance transformations of polyadic decompositions of matrix multiplication tensors define an equivalence relation on the set of such decompositions. In this paper, we present an algorithm to efficiently decide whether two polyadic decompositions of a given matrix multiplication tensor are equivalent. With this algorithm, we analyze the equivalence classes of decompositions of several matrix multiplication tensors. This analysis is relevant for the study of fast matrix multiplication as it relates to the question of how many essentially different fast matrix multiplication algorithms there exist. This question has been first studied by de~Groote, who showed that for the multiplication of $2\times2$ matrices with $7$ active multiplications, all algorithms are essentially equivalent to Strassen's algorithm. In contrast, the results of our analysis show that for the multiplication of larger matrices, (e.g., $2\times3$ by $3\times2$ or $3\times3$ by $3\times3$ matrices), two decompositions are very likely to be essentially different. We further provide a necessary criterion for a polyadic decomposition to be equivalent to a polyadic decomposition with integer entries. Decompositions with specific integer entries, e.g., powers of two, provide fast matrix multiplication algorithms with better efficiency and stability properties. This condition can be tested algorithmically and we present the conclusions obtained for the decompositions of small/medium matrix multiplication tensors.
Geometry of Arimoto Algorithm
Venue: arXiv cs.IT 2022
Year: 2022

In information theory, the channel capacity, which indicates how efficient a given channel is, plays an important role. The best-used algorithm for evaluating the channel capacity is Arimoto algorithm. This paper aims to reveal an information geometric structure of Arimoto algorithm. In the process of trying to reveal an information geometric structure of Arimoto algorithm, a new algorithm that monotonically increases the Kullback-Leibler divergence is proposed, which is called "the Backward em-algorithm." Since the Backward em-algorithm is available in many cases where we need to increase the Kullback-Leibler divergence, it has a lot of potential to be applied to many problems of statistics and information theory.
The Hairy Ball Problem is PPAD-Complete
Venue: arXiv cs.CC 2022
Year: 2022

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of (a) computing an approximate zero is PPAD-complete, and (b) computing an exact zero is FIXP-hard. We also consider the Hairy Ball Theorem on toroidal instead of spherical domains and show that the approximate problem remains PPAD-complete. On a conceptual level, our PPAD-membership results are particularly interesting, because they heavily rely on the investigation of multiple-source variants of END-OF-LINE, the canonical PPAD-complete problem. Our results on these new END-OF-LINE variants are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the IMBALANCE problem defined by Beame et al. in 1998.
Understanding Agent Incentives using Causal Influence Diagrams. Part I: Single Action Settings
Venue: arXiv cs.AI 2022
Year: 2022

Agents are systems that optimize an objective function in an environment. Together, the goal and the environment induce secondary objectives, incentives. Modeling the agent-environment interaction using causal influence diagrams, we can answer two fundamental questions about an agent's incentives directly from the graph: (1) which nodes can the agent have an incentivize to observe, and (2) which nodes can the agent have an incentivize to control? The answers tell us which information and influence points need extra protection. For example, we may want a classifier for job applications to not use the ethnicity of the candidate, and a reinforcement learning agent not to take direct control of its reward mechanism. Different algorithms and training paradigms can lead to different causal influence diagrams, so our method can be used to identify algorithms with problematic incentives and help in designing algorithms with better incentives.
Pancreas segmentation with probabilistic map guided bi-directional recurrent UNet
Venue: arXiv cs.CV 2022
Year: 2022

Pancreas segmentation in medical imaging data is of great significance for clinical pancreas diagnostics and treatment. However, the large population variations in the pancreas shape and volume cause enormous segmentation difficulties, even for state-of-the-art algorithms utilizing fully-convolutional neural networks (FCNs). Specifically, pancreas segmentation suffers from the loss of spatial information in 2D methods, and the high computational cost of 3D methods. To alleviate these problems, we propose a probabilistic-map-guided bi-directional recurrent UNet (PBR-UNet) architecture, which fuses intra-slice information and inter-slice probabilistic maps into a local 3D hybrid regularization scheme, which is followed by bi-directional recurrent network optimization. The PBR-UNet method consists of an initial estimation module for efficiently extracting pixel-level probabilistic maps and a primary segmentation module for propagating hybrid information through a 2.5D U-Net architecture. Specifically, local 3D information is inferred by combining an input image with the probabilistic maps of the adjacent slices into multichannel hybrid data, and then hierarchically aggregating the hybrid information of the entire segmentation network. Besides, a bi-directional recurrent optimization mechanism is developed to update the hybrid information in both the forward and the backward directions. This allows the proposed network to make full and optimal use of the local context information. Quantitative and qualitative evaluation was performed on the NIH Pancreas-CT dataset, and our proposed PBR-UNet method achieved better segmentation results with less computational cost compared to other state-of-the-art methods.
A Brain-inspired Algorithm for Training Highly Sparse Neural Networks
Venue: arXiv cs.NE 2022
Year: 2022

Sparse neural networks attract increasing interest as they exhibit comparable performance to their dense counterparts while being computationally efficient. Pruning the dense neural networks is among the most widely used methods to obtain a sparse neural network. Driven by the high training cost of such methods that can be unaffordable for a low-resource device, training sparse neural networks sparsely from scratch has recently gained attention. However, existing sparse training algorithms suffer from various issues, including poor performance in high sparsity scenarios, computing dense gradient information during training, or pure random topology search. In this paper, inspired by the evolution of the biological brain and the Hebbian learning theory, we present a new sparse training approach that evolves sparse neural networks according to the behavior of neurons in the network. Concretely, by exploiting the cosine similarity metric to measure the importance of the connections, our proposed method, Cosine similarity-based and Random Topology Exploration (CTRE), evolves the topology of sparse neural networks by adding the most important connections to the network without calculating dense gradient in the backward. We carried out different experiments on eight datasets, including tabular, image, and text datasets, and demonstrate that our proposed method outperforms several state-of-the-art sparse training algorithms in extremely sparse neural networks by a large gap. The implementation code is available on https://github.com/zahraatashgahi/CTRE
A Large-Scale Comparison of Tetrahedral and Hexahedral Elements for Solving Elliptic PDEs with the Finite Element Method
Venue: arXiv cs.NA 2022
Year: 2022

The Finite Element Method (FEM) is widely used to solve discrete Partial Differential Equations (PDEs) in engineering and graphics applications. The popularity of FEM led to the development of a large family of variants, most of which require a tetrahedral or hexahedral mesh to construct the basis. While the theoretical properties of FEM basis (such as convergence rate, stability, etc.) are well understood under specific assumptions on the mesh quality, their practical performance, influenced both by the choice of the basis construction and quality of mesh generation, have not been systematically documented for large collections of automatically meshed 3D geometries. We introduce a set of benchmark problems involving most commonly solved elliptic PDEs, starting from simple cases with an analytical solution, moving to commonly used test problem setups, and using manufactured solutions for thousands of real-world, automatically meshed geometries. For all these cases, we use state-of-the-art meshing tools to create both tetrahedral and hexahedral meshes, and compare the performance of different element types for common elliptic PDEs. The goal of his benchmark is to enable comparison of complete FEM pipelines, from mesh generation to algebraic solver, and exploration of relative impact of different factors on the overall system performance.
Trifocal Relative Pose from Lines at Points and its Efficient Solution
Venue: arXiv cs.CV 2022
Year: 2022

We present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of i) three points and one line and the novel case of ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Groebner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver framework MINUS, which dramatically speeds up previous HC solving by specializing HC methods to generic cases of our problems. We characterize their number of solutions and show with simulated experiments that our solvers are numerically robust and stable under image noise, a key contribution given the borderline intractable degree of nonlinearity of trinocular constraints. We show in real experiments that i) SIFT feature location and orientation provide good enough point-and-line correspondences for three-view reconstruction and ii) that we can solve difficult cases with too few or too noisy tentative matches, where the state of the art structure from motion initialization fails.
On the Theory of Dynamic Graph Regression Problem
Venue: arXiv cs.LG 2022
Year: 2022

Most of real-world graphs are dynamic, i.e., they change over time by a sequence of update operations. While the regression problem has been studied for static graphs and temporal graphs, it is not investigated for general dynamic graphs. In this paper, we study regression over dynamic graphs. First, we present the notion of update-efficient matrix embedding, that defines conditions sufficient for a matrix embedding to be effectively used for dynamic graph regression (under l2 norm). Then, we show that given a n*m update-efficient matrix embedding (e.g., the adjacency matrix) and after an update operation in the graph, the exact optimal solution of linear regression can be updated in O(nm) time for the revised graph. Moreover, we show that this also holds when the matrix embedding is the Laplacian matrix and the update operations are restricted to edge insertion/deletion. In the end, by conducting experiments over synthetic and real-world graphs, we show the high efficiency of updating the solution of graph regression.
Motion Deblurring with an Adaptive Network
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we address the problem of dynamic scene deblurring in the presence of motion blur. Restoration of images affected by severe blur necessitates a network design with a large receptive field, which existing networks attempt to achieve through simple increment in the number of generic convolution layers, kernel-size, or the scales at which the image is processed. However, increasing the network capacity in this manner comes at the expense of increase in model size and inference speed, and ignoring the non-uniform nature of blur. We present a new architecture composed of spatially adaptive residual learning modules that implicitly discover the spatially varying shifts responsible for non-uniform blur in the input image and learn to modulate the filters. This capability is complemented by a self-attentive module which captures non-local relationships among the intermediate features and enhances the receptive field. We then incorporate a spatiotemporal recurrent module in the design to also facilitate efficient video deblurring. Our networks can implicitly model the spatially-varying deblurring process, while dispensing with multi-scale processing and large filters entirely. Extensive qualitative and quantitative comparisons with prior art on benchmark dynamic scene deblurring datasets clearly demonstrate the superiority of the proposed networks via reduction in model-size and significant improvements in accuracy and speed, enabling almost real-time deblurring.
ThunderNet: Towards Real-time Generic Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Real-time generic object detection on mobile platforms is a crucial but challenging computer vision task. However, previous CNN-based detectors suffer from enormous computational cost, which hinders them from real-time inference in computation-constrained scenarios. In this paper, we investigate the effectiveness of two-stage detectors in real-time generic detection and propose a lightweight two-stage detector named ThunderNet. In the backbone part, we analyze the drawbacks in previous lightweight backbones and present a lightweight backbone designed for object detection. In the detection part, we exploit an extremely efficient RPN and detection head design. To generate more discriminative feature representation, we design two efficient architecture blocks, Context Enhancement Module and Spatial Attention Module. At last, we investigate the balance between the input resolution, the backbone, and the detection head. Compared with lightweight one-stage detectors, ThunderNet achieves superior performance with only 40% of the computational cost on PASCAL VOC and COCO benchmarks. Without bells and whistles, our model runs at 24.1 fps on an ARM-based device. To the best of our knowledge, this is the first real-time detector reported on ARM platforms. Our code and models are available at \url{https://github.com/qinzheng93/ThunderNet}.
MedGCN: Medication recommendation and lab test imputation via graph convolutional networks
Venue: arXiv cs.LG 2022
Year: 2022

Laboratory testing and medication prescription are two of the most important routines in daily clinical practice. Developing an artificial intelligence system that can automatically make lab test imputations and medication recommendations can save costs on potentially redundant lab tests and inform physicians of a more effective prescription. We present an intelligent medical system (named MedGCN) that can automatically recommend the patients' medications based on their incomplete lab tests, and can even accurately estimate the lab values that have not been taken. In our system, we integrate the complex relations between multiple types of medical entities with their inherent features in a heterogeneous graph. Then we model the graph to learn a distributed representation for each entity in the graph based on graph convolutional networks (GCN). By the propagation of graph convolutional networks, the entity representations can incorporate multiple types of medical information that can benefit multiple medical tasks. Moreover, we introduce a cross regularization strategy to reduce overfitting for multi-task training by the interaction between the multiple tasks. In this study, we construct a graph to associate 4 types of medical entities, i.e., patients, encounters, lab tests, and medications, and applied a graph neural network to learn node embeddings for medication recommendation and lab test imputation. we validate our MedGCN model on two real-world datasets: NMEDW and MIMIC-III. The experimental results on both datasets demonstrate that our model can outperform the state-of-the-art in both tasks. We believe that our innovative system can provide a promising and reliable way to assist physicians to make medication prescriptions and to save costs on potentially redundant lab tests.
On the Power and Limitations of Random Features for Understanding Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Recently, a spate of papers have provided positive theoretical results for training over-parameterized neural networks (where the network size is larger than what is needed to achieve low error). The key insight is that with sufficient over-parameterization, gradient-based methods will implicitly leave some components of the network relatively unchanged, so the optimization dynamics will behave as if those components are essentially fixed at their initial random values. In fact, fixing these explicitly leads to the well-known approach of learning with random features. In other words, these techniques imply that we can successfully learn with neural networks, whenever we can successfully learn with random features. In this paper, we first review these techniques, providing a simple and self-contained analysis for one-hidden-layer networks. We then argue that despite the impressive positive results, random feature approaches are also inherently limited in what they can explain. In particular, we rigorously show that random features cannot be used to learn even a single ReLU neuron with standard Gaussian inputs, unless the network size (or magnitude of the weights) is exponentially large. Since a single neuron is learnable with gradient-based methods, we conclude that we are still far from a satisfying general explanation for the empirical success of neural networks.