OpenRaiser/Intern-Atlas huggingface dataset:
Convergence rates for the joint solution of inverse problems with compressed sensing data
Venue: arXiv cs.IT 2022
Year: 2022

Compressed sensing (CS) is a powerful tool for reducing the amount of data to be collected while maintaining high spatial resolution. Such techniques work well in practice and at the same time are supported by solid theory. Standard CS results assume measurements to be made directly on the targeted signal. In many practical applications, however, CS information can only be taken from indirect data $h_\star = W x_\star$ related to the original signal by an additional forward operator. If inverting the forward operator is ill-posed, then existing CS theory is not applicable. In this paper, we address this issue and present two joint reconstruction approaches, namely relaxed $\ell^1$ co-regularization and strict $\ell^1$ co-regularization, for CS from indirect data. As main results, we derive error estimates for recovering $x_\star$ and $h_\star$. In particular, we derive a linear convergence rate in the norm for the latter. To obtain these results, solutions are required to satisfy a source condition and the CS measurement operator is required to satisfy a restricted injectivity condition. We further show that these conditions are not only sufficient but even necessary to obtain linear convergence.
Toward Causal-Aware RL: State-Wise Action-Refined Temporal Difference
Venue: arXiv cs.LG 2022
Year: 2022

Although it is well known that exploration plays a key role in Reinforcement Learning (RL), prevailing exploration strategies for continuous control tasks in RL are mainly based on naive isotropic Gaussian noise regardless of the causality relationship between action space and the task and consider all dimensions of actions equally important. In this work, we propose to conduct interventions on the primal action space to discover the causal relationship between the action space and the task reward. We propose the method of State-Wise Action Refined (SWAR), which addresses the issue of action space redundancy and promote causality discovery in RL. We formulate causality discovery in RL tasks as a state-dependent action space selection problem and propose two practical algorithms as solutions. The first approach, TD-SWAR, detects task-related actions during temporal difference learning, while the second approach, Dyn-SWAR, reveals important actions through dynamic model prediction. Empirically, both methods provide approaches to understand the decisions made by RL agents and improve learning efficiency in action-redundant tasks.
Establishing Strong Baselines for TripClick Health Retrieval
Venue: arXiv cs.IR 2022
Year: 2022

We present strong Transformer-based re-ranking and dense retrieval baselines for the recently released TripClick health ad-hoc retrieval collection. We improve the - originally too noisy - training data with a simple negative sampling policy. We achieve large gains over BM25 in the re-ranking task of TripClick, which were not achieved with the original baselines. Furthermore, we study the impact of different domain-specific pre-trained models on TripClick. Finally, we show that dense retrieval outperforms BM25 by considerable margins, even with simple training procedures.
Decoding Nonbinary LDPC Codes via Proximal-ADMM Approach (include convergence proofs)
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code's length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders.
ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions
Venue: arXiv cs.LG 2022
Year: 2022

Outlier detection refers to the identification of data points that deviate from a general data distribution. Existing unsupervised approaches often suffer from high computational cost, complex hyperparameter tuning, and limited interpretability, especially when working with large, high-dimensional datasets. To address these issues, we present a simple yet effective algorithm called ECOD (Empirical-Cumulative-distribution-based Outlier Detection), which is inspired by the fact that outliers are often the "rare events" that appear in the tails of a distribution. In a nutshell, ECOD first estimates the underlying distribution of the input data in a nonparametric fashion by computing the empirical cumulative distribution per dimension of the data. ECOD then uses these empirical distributions to estimate tail probabilities per dimension for each data point. Finally, ECOD computes an outlier score of each data point by aggregating estimated tail probabilities across dimensions. Our contributions are as follows: (1) we propose a novel outlier detection method called ECOD, which is both parameter-free and easy to interpret; (2) we perform extensive experiments on 30 benchmark datasets, where we find that ECOD outperforms 11 state-of-the-art baselines in terms of accuracy, efficiency, and scalability; and (3) we release an easy-to-use and scalable (with distributed support) Python implementation for accessibility and reproducibility.
Fast and High-Quality Image Denoising via Malleable Convolutions
Venue: arXiv cs.CV 2022
Year: 2022

Most image denoising networks apply a single set of static convolutional kernels across the entire input image. This is sub-optimal for natural images, as they often consist of heterogeneous visual patterns. Dynamic convolution tries to address this issue by using per-pixel convolution kernels, but this greatly increases computational cost. In this work, we present Malleable Convolution (MalleConv), which performs spatial-varying processing with minimal computational overhead. MalleConv uses a smaller set of spatially-varying convolution kernels, a compromise between static and per-pixel convolution kernels. These spatially-varying kernels are produced by an efficient predictor network running on a downsampled input, making them much more efficient to compute than per-pixel kernels produced by a full-resolution image, and also enlarging the network's receptive field compared with static kernels. These kernels are then jointly upsampled and applied to a full-resolution feature map through an efficient on-the-fly slicing operator with minimum memory overhead. To demonstrate the effectiveness of MalleConv, we use it to build an efficient denoising network we call MalleNet. MalleNet achieves high-quality results without very deep architectures, making it 8.9x faster than the best performing denoising algorithms while achieving similar visual quality. We also show that a single MalleConv layer added to a standard convolution-based backbone can significantly reduce the computational cost or boost image quality at a similar cost. More information is on our project page: \url{https://yifanjiang.net/MalleConv.html}
VISAS -- Detecting GPS spoofing attacks against drones by analyzing camera's video stream
Venue: arXiv cs.CR 2022
Year: 2022

In this study, we propose an innovative method for the real-time detection of GPS spoofing attacks targeting drones, based on the video stream captured by a drone's camera. The proposed method collects frames from the video stream and their location (GPS); by calculating the correlation between each frame, our method can identify an attack on a drone. We first analyze the performance of the suggested method in a controlled environment by conducting experiments on a flight simulator that we developed. Then, we analyze its performance in the real world using a DJI drone. Our method can provide different levels of security against GPS spoofing attacks, depending on the detection interval required; for example, it can provide a high level of security to a drone flying at an altitude of 50-100 meters over an urban area at an average speed of 4 km/h in conditions of low ambient light; in this scenario, the method can provide a level of security that detects any GPS spoofing attack in which the spoofed location is a distance of 1-4 meters (an average of 2.5 meters) from the real location.
D-Former: A U-shaped Dilated Transformer for 3D Medical Image Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Computer-aided medical image segmentation has been applied widely in diagnosis and treatment to obtain clinically useful information of shapes and volumes of target organs and tissues. In the past several years, convolutional neural network (CNN) based methods (e.g., U-Net) have dominated this area, but still suffered from inadequate long-range information capturing. Hence, recent work presented computer vision Transformer variants for medical image segmentation tasks and obtained promising performances. Such Transformers model long-range dependency by computing pair-wise patch relations. However, they incur prohibitive computational costs, especially on 3D medical images (e.g., CT and MRI). In this paper, we propose a new method called Dilated Transformer, which conducts self-attention for pair-wise patch relations captured alternately in local and global scopes. Inspired by dilated convolution kernels, we conduct the global self-attention in a dilated manner, enlarging receptive fields without increasing the patches involved and thus reducing computational costs. Based on this design of Dilated Transformer, we construct a U-shaped encoder-decoder hierarchical architecture called D-Former for 3D medical image segmentation. Experiments on the Synapse and ACDC datasets show that our D-Former model, trained from scratch, outperforms various competitive CNN-based or Transformer-based segmentation models at a low computational cost without time-consuming per-training process.
Benchmark Functions for CEC 2022 Competition on Seeking Multiple Optima in Dynamic Environments
Venue: arXiv cs.NE 2022
Year: 2022

Dynamic and multimodal features are two important properties and widely existed in many real-world optimization problems. The former illustrates that the objectives and/or constraints of the problems change over time, while the latter means there is more than one optimal solution (sometimes including the accepted local solutions) in each environment. The dynamic multimodal optimization problems (DMMOPs) have both of these characteristics, which have been studied in the field of evolutionary computation and swarm intelligence for years, and attract more and more attention. Solving such problems requires optimization algorithms to simultaneously track multiple optima in the changing environments. So that the decision makers can pick out one optimal solution in each environment according to their experiences and preferences, or quickly turn to other solutions when the current one cannot work well. This is very helpful for the decision makers, especially when facing changing environments. In this competition, a test suit about DMMOPs is given, which models the real-world applications. Specifically, this test suit adopts 8 multimodal functions and 8 change modes to construct 24 typical dynamic multimodal optimization problems. Meanwhile, the metric is also given to measure the algorithm performance, which considers the average number of optimal solutions found in all environments. This competition will be very helpful to promote the development of dynamic multimodal optimization algorithms.
A New Modeling of Classical Folds in Computational Origami
Venue: arXiv cs.CG 2022
Year: 2022

This paper shows a cut along a crease on an origami sheet makes simple modeling of popular traditional basic folds such as a squash fold in computational origami. The cut operation can be applied to other classical folds and significantly simplify their modeling and subsequent implementation in the context of computational origami.
Automated Generation of Illustrations for Synthetic Geometry Proofs
Venue: arXiv cs.LO 2022
Year: 2022

We report on a new, simple, modular, and flexible approach for automated generation of illustrations for (readable) synthetic geometry proofs. The underlying proofs are generated using the Larus automated prover for coherent logic, and corresponding illustrations are generated in the GCLC language. Animated illustrations are also supported.
Spreads and Packings of PG(3,2), Formally!
Venue: arXiv cs.LO 2022
Year: 2022

We study how to formalize in the Coq proof assistant the smallest projective space PG(3,2). We then describe formally the spreads and packings of PG(3,2), as well as some of their properties. The formalization is rather straightforward, however as the number of objects at stake increases rapidly, we need to exploit some symmetry arguments as well as smart proof techniques to make proof search and verification faster and thus tractable using the Coq proof assistant. This work can be viewed as a first step towards formalizing projective spaces of higher dimension, e.g. PG(4,2), or larger order, e.g. PG(3,3).
Deep Learning for GPS Spoofing Detection in Cellular Enabled Unmanned Aerial Vehicle Systems
Venue: arXiv cs.CR 2022
Year: 2022

Cellular-based Unmanned Aerial Vehicle (UAV) systems are a promising paradigm to provide reliable and fast Beyond Visual Line of Sight (BVLoS) communication services for UAV operations. However, such systems are facing a serious GPS spoofing threat for UAV's position. To enable safe and secure UAV navigation BVLoS, this paper proposes a cellular network assisted UAV position monitoring and anti-GPS spoofing system, where deep learning approach is used to live detect spoofed GPS positions. Specifically, the proposed system introduces a MultiLayer Perceptron (MLP) model which is trained on the statistical properties of path loss measurements collected from nearby base stations to decide the authenticity of the GPS position. Experiment results indicate the accuracy rate of detecting GPS spoofing under our proposed approach is more than 93% with three base stations and it can also reach 80% with only one base station.
A Queuing based Dynamic Auto Scaling Algorithm for the LTE EPC Control Plane
Venue: arXiv cs.NI 2022
Year: 2022

Network Slicing (NS) is expected to be a key functionality of the upcoming 5G systems. Coupled with Software Defined Networking (SDN) and Network Function Virtualization (NFV),NS will enable a flexible deployment of Network Functions belonging to multiple Service Function Chains (SFC) over a shared infrastructure. To address the complexities that arise from this new environment, we formulate a MILP optimization model that enables a cost-optimal deployment of network slices, allowing a Mobile Network Operator to efficiently allocate the underlying layer resources according to the users' requirements. For each network slice, the proposed solution guarantees the required delay and the bandwidth, while efficiently handling the usage of underlying nodes, which leads to reduced cost. The obtained results show the efficiency of the proposed solution in terms of cost and execution time for small-scale networks, while it shows an interesting behavior in the large-scale topologies.
A New Algorithm for Pyramidal Clipping of Line Segments in E3
Venue: arXiv cs.CG 2022
Year: 2022

A new algorithm for clipping a line segment against a pyramid in E3 is presented. This algorithm avoids computation of intersection points which are not end-points of the output line segment. It also allows solving all cases more effectively. The performance of this algorithm is shown to be consistently better than existing algorithms, including the Cohen-Sutherland, Liang-Barsky and Cyrus-Beck algorithms.
Two New Algorithms for Line Clipping in E2 and Their Comparison
Venue: arXiv cs.CG 2022
Year: 2022

Many algorithms for clipping a line by a rectangular area or a convex polygon in E2 or by a non-convex or convex polyhedron in E3 have been published. The line segment clipping by the rectangular window in E2 is often restricted to the use of the Cohen-Sutherland (CS) algorithm or its modifications based on some presumptions like small clipping window or more sophisticated coding technique, etc. The line clipping problem solution is a bottleneck of many packages and applications and, therefore, it would be desirable to use the fastest algorithm even though it is more complex.
Line Clipping in E3 with Expected Complexity O(1)
Venue: arXiv cs.CG 2022
Year: 2022

A new line clipping algorithm against convex polyhedron in E3 with an expected complexity O(1) is presented. The suggested approach is based on two orthogonal projections to E2 co-ordinate system and on pre-processing of the given polyhedron. The pre-processing enables to speed up solution significantly. The proposed method is convenient for those applications when many lines are clipped against constant convex polyhedron. Theoretical considerations and experimental results are also presented.
A Priority-Aware Multiqueue NIC Design
Venue: arXiv cs.NI 2022
Year: 2022

Low-level embedded systems are used to control cyber-phyiscal systems in industrial and autonomous applications. They need to meet hard real-time requirements as unanticipated controller delays on moving machines can have devastating effects. Modern developments such as the industrial Internet of Things and autonomous machines require these devices to connect to large IP networks. Since Network Interface Controllers (NICs) trigger interrupts for incoming packets, real-time embedded systems are subject to unpredictable preemptions when connected to such networks. In this work, we propose a priority-aware NIC design to moderate network-generated interrupts by mapping IP flows to processes and based on that, consolidates their packets into different queues. These queues apply priority-dependent interrupt moderation. First experimental evaluations show that 93% of interrupts can be saved leading to an 80% decrease of processing delay of critical tasks in the configurations investigated.
Semi-supervised Stance Detection of Tweets Via Distant Network Supervision
Venue: arXiv cs.SI 2022
Year: 2022

Detecting and labeling stance in social media text is strongly motivated by hate speech detection, poll prediction, engagement forecasting, and concerted propaganda detection. Today's best neural stance detectors need large volumes of training data, which is difficult to curate given the fast-changing landscape of social media text and issues on which users opine. Homophily properties over the social network provide strong signal of coarse-grained user-level stance. But semi-supervised approaches for tweet-level stance detection fail to properly leverage homophily. In light of this, We present SANDS, a new semi-supervised stance detector. SANDS starts from very few labeled tweets. It builds multiple deep feature views of tweets. It also uses a distant supervision signal from the social network to provide a surrogate loss signal to the component learners. We prepare two new tweet datasets comprising over 236,000 politically tinted tweets from two demographics (US and India) posted by over 87,000 users, their follower-followee graph, and over 8,000 tweets annotated by linguists. SANDS achieves a macro-F1 score of 0.55 (0.49) on US (India)-based datasets, outperforming 17 baselines (including variants of SANDS) substantially, particularly for minority stance labels and noisy text. Numerous ablation experiments on SANDS disentangle the dynamics of textual and network-propagated stance signals.
A Systematic Approach towards Efficient Private Matrix Multiplication
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problems of Private and Secure Matrix Multiplication (PSMM) and Fully Private Matrix Multiplication (FPMM), for which matrices privately selected by a master node are multiplied at distributed worker nodes without revealing the indices of the selected matrices, even when a certain number of workers collude with each other. We propose a novel systematic approach to solve PSMM and FPMM with colluding workers, which leverages solutions to a related Secure Matrix Multiplication (SMM) problem where the data (rather than the indices) of the multiplied matrices are kept private from colluding workers. Specifically, given an SMM strategy based on polynomial codes or Lagrange codes, one can exploit the special structure inspired by the matrix encoding function to design private coded queries for PSMM/FPMM, such that the algebraic structure of the computation result at each worker resembles that of the underlying SMM strategy. Adopting this systematic approach provides novel insights in private query designs for private matrix multiplication, substantially simplifying the processes of designing PSMM and FPMM strategies. Furthermore, the PSMM and FPMM strategies constructed following the proposed approach outperform the state-of-the-art strategies in one or more performance metrics including recovery threshold (minimal number of workers the master needs to wait for before correctly recovering the multiplication result), communication cost, and computation complexity, demonstrating a more flexible tradeoff in optimizing system efficiency.
Multimodal Entity Tagging with Multimodal Knowledge Base
Venue: arXiv cs.IR 2022
Year: 2022

To enhance research on multimodal knowledge base and multimodal information processing, we propose a new task called multimodal entity tagging (MET) with a multimodal knowledge base (MKB). We also develop a dataset for the problem using an existing MKB. In an MKB, there are entities and their associated texts and images. In MET, given a text-image pair, one uses the information in the MKB to automatically identify the related entity in the text-image pair. We solve the task by using the information retrieval paradigm and implement several baselines using state-of-the-art methods in NLP and CV. We conduct extensive experiments and make analyses on the experimental results. The results show that the task is challenging, but current technologies can achieve relatively high performance. We will release the dataset, code, and models for future research.