OpenRaiser/Intern-Atlas huggingface dataset:
Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation From Undersampled Data
Venue: arXiv cs.NA 2022
Year: 2022

Subspace learning and matrix factorization problems have great many applications in science and engineering, and efficient algorithms are critical as dataset sizes continue to grow. Many relevant problem formulations are non-convex, and in a variety of contexts it has been observed that solving the non-convex problem directly is not only efficient but reliably accurate. We discuss convergence theory for a particular method: first order incremental gradient descent constrained to the Grassmannian. The output of the algorithm is an orthonormal basis for a $d$-dimensional subspace spanned by an input streaming data matrix. We study two sampling cases: where each data vector of the streaming matrix is fully sampled, or where it is undersampled by a sampling matrix $A_t\in \mathbb{R}^{m\times n}$ with $m\ll n$. Our results cover two cases, where $A_t$ is Gaussian or a subset of rows of the identity matrix. We propose an adaptive stepsize scheme that depends only on the sampled data and algorithm outputs. We prove that with fully sampled data, the stepsize scheme maximizes the improvement of our convergence metric at each iteration, and this method converges from any random initialization to the true subspace, despite the non-convex formulation and orthogonality constraints. For the case of undersampled data, we establish monotonic expected improvement on the defined convergence metric for each iteration with high probability.
On Finite-Index Indexed Grammars and Their Restrictions
Venue: arXiv cs.FL 2022
Year: 2022

The family, L(INDLIN), of languages generated by linear indexed grammars has been studied in the literature. It is known that the Parikh image of every language in L(INDLIN) is semi-linear. However, there are bounded semi linear languages that are not in L(INDLIN). Here, we look at larger families of (restricted) indexed languages and study their properties, their relationships, and their decidability properties.
An Evaluation Framework and Database for MoCap-Based Gait Recognition Methods
Venue: arXiv cs.CV 2022
Year: 2022

As a contribution to reproducible research, this paper presents a framework and a database to improve the development, evaluation and comparison of methods for gait recognition from motion capture (MoCap) data. The evaluation framework provides implementation details and source codes of state-of-the-art human-interpretable geometric features as well as our own approaches where gait features are learned by a modification of Fisher's Linear Discriminant Analysis with the Maximum Margin Criterion, and by a combination of Principal Component Analysis and Linear Discriminant Analysis. It includes a description and source codes of a mechanism for evaluating four class separability coefficients of feature space and four rank-based classifier performance metrics. This framework also contains a tool for learning a custom classifier and for classifying a custom query on a custom gallery. We provide an experimental database along with source codes for its extraction from the general CMU MoCap database.
Cascaded Incremental Nonlinear Dynamic Inversion Control for MAV Disturbance Rejection
Venue: arXiv cs.RO 2022
Year: 2022

Micro Aerial Vehicles (MAVs) are limited in their operation outdoors near obstacles by their ability to withstand wind gusts. Currently widespread position control methods such as Proportional Integral Derivative control do not perform well under the influence of gusts. Incremental Nonlinear Dynamic Inversion (INDI) is a sensor-based control technique that can control nonlinear systems subject to disturbances. It was developed for the attitude control of manned aircraft or MAVs. In this paper we generalize this method to the outer loop control of MAVs under severe gust loads. Significant improvements over a traditional Proportional Integral Derivative (PID) controller are demonstrated in an experiment where the quadrotor flies in and out of a windtunnel exhaust at 10 m/s. The control method does not rely on frequent position updates, as is demonstrated in an outside experiment using a standard GPS module. Finally, we investigate the effect of using a linearization to calculate thrust vector increments, compared to a nonlinear calculation. The method requires little modeling and is computationally efficient.
A Semantic Account of Metric Preservation
Venue: arXiv cs.PL 2022
Year: 2022

Program sensitivity measures how robust a program is to small changes in its input, and is a fundamental notion in domains ranging from differential privacy to cyber-physical systems. A natural way to formalize program sensitivity is in terms of metrics on the input and output spaces, requiring that an $r$-sensitive function map inputs that are at distance $d$ to outputs that are at distance at most $r \cdot d$. Program sensitivity is thus an analogue of Lipschitz continuity for programs. Reed and Pierce introduced Fuzz, a functional language with a linear type system that can express program sensitivity. They show soundness operationally, in the form of a metric preservation property. Inspired by their work, we study program sensitivity and metric preservation from a denotational point of view. In particular, we introduce metric CPOs, a novel semantic structure for reasoning about computation on metric spaces, by endowing CPOs with a compatible notion of distance. This structure is useful for reasoning about metric properties of programs, and specifically about program sensitivity. We demonstrate metric CPOs by giving a model for the deterministic fragment of Fuzz.
Property Testing of Joint Distributions using Conditional Samples
Venue: arXiv cs.CC 2022
Year: 2022

In this paper, we consider the problem of testing properties of joint distributions under the Conditional Sampling framework. In the standard sampling model, the sample complexity of testing properties of joint distributions is exponential in the dimension, resulting in inefficient algorithms for practical use. While recent results achieve efficient algorithms for product distributions with significantly smaller sample complexity, no efficient algorithm is expected when the marginals are not independent. We initialize the study of conditional sampling in the multidimensional setting. We propose a subcube conditional sampling model where the tester can condition on an (adaptively) chosen subcube of the domain. Due to its simplicity, this model is potentially implementable in many practical applications, particularly when the distribution is a joint distribution over $Σ^n$ for some set $Σ$. We present algorithms for various fundamental properties of distributions in the subcube-conditioning model and prove that the sample complexity is polynomial in the dimension $n$ (and not exponential as in the traditional model). We present an algorithm for testing identity to a known distribution using $\tilde{\mathcal{O}}(n^2)$-subcube-conditional samples, an algorithm for testing identity between two unknown distributions using $\tilde{\mathcal{O}}(n^5)$-subcube-conditional samples and an algorithm for testing identity to a product distribution using $tilde{\mathcal{O}}(n^5)$-subcube-conditional samples. The central concept of our technique involves an elegant chain rule which can be proved using basic techniques of probability theory yet powerful enough to avoid the curse of dimensionality.
Defective Coloring on Classes of Perfect Graphs
Venue: arXiv cs.DS 2022
Year: 2022

In Defective Coloring we are given a graph $G$ and two integers $χ_d$, $Δ^*$ and are asked if we can $χ_d$-color $G$ so that the maximum degree induced by any color class is at most $Δ^*$. We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters $χ_d$, $Δ^*$ is set to the smallest possible fixed value that does not trivialize the problem ($χ_d = 2$ or $Δ^* = 1$). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs. We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either $χ_d$ or $Δ^*$ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both $χ_d$ and $Δ^*$ are unbounded.
Consistency of orthology and paralogy constraints in the presence of gene transfers
Venue: arXiv cs.DS 2022
Year: 2022

Orthology and paralogy relations are often inferred by methods based on gene similarity, which usually yield a graph depicting the relationships between gene pairs. Such relation graphs are known to frequently contain errors, as they cannot be explained via a gene tree that both contains the depicted orthologs/paralogs, and that is consistent with a species tree $S$. This idea of detecting errors through inconsistency with a species tree has mostly been studied in the presence of speciation and duplication events only. In this work, we ask: could the given set of relations be consistent if we allow lateral gene transfers in the evolutionary model? We formalize this question and provide a variety of algorithmic results regarding the underlying problems. Namely, we show that deciding if a relation graph $R$ is consistent with a given species network $N$ is NP-hard, and that it is W[1]-hard under the parameter "minimum number of transfers". However, we present an FPT algorithm based on the degree of the $DS$-tree associated with $R$. We also study analogous problems in the case that the transfer highways on a species tree are unknown.
Dynamic Switching Networks: A Dynamic, Non-local, and Time-independent Approach to Emergence
Venue: arXiv cs.MA 2022
Year: 2022

The concept of emergence is a powerful concept to explain very complex behaviour by simple underling rules. Existing approaches of producing emergent collective behaviour have many limitations making them unable to account for the complexity we see in the real world. In this paper we propose a new dynamic, non-local, and time independent approach that uses a network like structure to implement the laws or the rules, where the mathematical equations representing the rules are converted to a series of switching decisions carried out by the network on the particles moving in the network. The proposed approach is used to generate patterns with different types of symmetry.
Applying Data Augmentation to Handwritten Arabic Numeral Recognition Using Deep Learning Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Handwritten character recognition has been the center of research and a benchmark problem in the sector of pattern recognition and artificial intelligence, and it continues to be a challenging research topic. Due to its enormous application many works have been done in this field focusing on different languages. Arabic, being a diversified language has a huge scope of research with potential challenges. A convolutional neural network model for recognizing handwritten numerals in Arabic language is proposed in this paper, where the dataset is subject to various augmentation in order to add robustness needed for deep learning approach. The proposed method is empowered by the presence of dropout regularization to do away with the problem of data overfitting. Moreover, suitable change is introduced in activation function to overcome the problem of vanishing gradient. With these modifications, the proposed system achieves an accuracy of 99.4\% which performs better than every previous work on the dataset.
Extending rational choice behavior: The decision problem for Boolean set theory with a choice correspondence
Venue: arXiv cs.LO 2022
Year: 2022

Given the family $P$ of all nonempty subsets of a set $U$ of alternatives, a choice over $U$ is a function $c \colon Ω\to P$ such that $Ω\subseteq P$ and $c(B) \subseteq B$ for all menus $B \in Ω$. A choice is total if $Ω= P$, and partial otherwise. In economics, an agent is considered rational whenever her choice behavior satisfies suitable axioms of consistency, which are properties quantified over menus. Here we address the following lifting problem: Given a partial choice satisfying one or more axioms of consistency, is it possible to extend it to a total choice satisfying the same axioms? After characterizing the lifting of some choice properties that are well-known in the economics literature, we study the decidability of the connected satisfiability problem for unquantified formulae of an elementary fragment of set theory, which involves a choice function symbol, the Boolean set operators, the singleton, the equality and inclusion predicates, and the propositional connectives. In two cases we prove that the satisfiability problem is NP-complete, whereas in the remaining cases we obtain NP-completeness under the additional assumption that the number of choice terms is constant.
Audio-Visual Speech Enhancement Using Multimodal Deep Convolutional Neural Networks
Venue: arXiv cs.SD 2022
Year: 2022

Speech enhancement (SE) aims to reduce noise in speech signals. Most SE techniques focus only on addressing audio information. In this work, inspired by multimodal learning, which utilizes data from different modalities, and the recent success of convolutional neural networks (CNNs) in SE, we propose an audio-visual deep CNNs (AVDCNN) SE model, which incorporates audio and visual streams into a unified network model. We also propose a multi-task learning framework for reconstructing audio and visual signals at the output layer. Precisely speaking, the proposed AVDCNN model is structured as an audio-visual encoder-decoder network, in which audio and visual data are first processed using individual CNNs, and then fused into a joint network to generate enhanced speech (the primary task) and reconstructed images (the secondary task) at the output layer. The model is trained in an end-to-end manner, and parameters are jointly learned through back-propagation. We evaluate enhanced speech using five instrumental criteria. Results show that the AVDCNN model yields a notably superior performance compared with an audio-only CNN-based SE model and two conventional SE approaches, confirming the effectiveness of integrating visual information into the SE process. In addition, the AVDCNN model also outperforms an existing audio-visual SE model, confirming its capability of effectively combining audio and visual information in SE.
Acceleration of Histogram-Based Contrast Enhancement via Selective Downsampling
Venue: arXiv cs.MM 2022
Year: 2022

In this paper, we propose a general framework to accelerate the universal histogram-based image contrast enhancement (CE) algorithms. Both spatial and gray-level selective down-sampling of digital images are adopted to decrease computational cost, while the visual quality of enhanced images is still preserved and without apparent degradation. Mapping function calibration is novelly proposed to reconstruct the pixel mapping on the gray levels missed by downsampling. As two case studies, accelerations of histogram equalization (HE) and the state-of-the-art global CE algorithm, i.e., spatial mutual information and PageRank (SMIRANK), are presented detailedly. Both quantitative and qualitative assessment results have verified the effectiveness of our proposed CE acceleration framework. In typical tests, computational efficiencies of HE and SMIRANK have been speeded up by about 3.9 and 13.5 times, respectively.
What Words Do We Use to Lie?: Word Choice in Deceptive Messages
Venue: arXiv cs.CL 2022
Year: 2022

Text messaging is the most widely used form of computer-mediated communication (CMC). Previous findings have shown that linguistic factors can reliably indicate messages as deceptive. For example, users take longer and use more words to craft deceptive messages than they do truthful messages. Existing research has also examined how factors, such as student status and gender, affect rates of deception and word choice in deceptive messages. However, this research has been limited by small sample sizes and has returned contradicting findings. This paper aims to address these issues by using a dataset of text messages collected from a large and varied set of participants using an Android messaging application. The results of this paper show significant differences in word choice and frequency of deceptive messages between male and female participants, as well as between students and non-students.
Disjunctive bases: normal forms and model theory for modal logics
Venue: arXiv cs.LO 2022
Year: 2022

We present the concept of a disjunctive basis as a generic framework for normal forms in modal logic based on coalgebra. Disjunctive bases were defined in previous work on completeness for modal fixpoint logics, where they played a central role in the proof of a generic completeness theorem for coalgebraic mu-calculi. Believing the concept has a much wider significance, here we investigate it more thoroughly in its own right. We show that the presence of a disjunctive basis at the "one-step" level entails a number of good properties for a coalgebraic mu-calculus, in particular, a simulation theorem showing that every alternating automaton can be transformed into an equivalent nondeterministic one. Based on this, we prove a Lyndon theorem for the full fixpoint logic, its fixpoint-free fragment and its one-step fragment, and a Uniform Interpolation result, for both the full mu-calculus and its fixpoint-free fragment. We also raise the questions, when a disjunctive basis exists, and how disjunctive bases are related to Moss' coalgebraic "nabla" modalities. Nabla formulas provide disjunctive bases for many coalgebraic modal logics, but there are cases where disjunctive bases give useful normal forms even when nabla formulas fail to do so, our prime example being graded modal logic. We also show that disjunctive bases are preserved by forming sums, products and compositions of coalgebraic modal logics, providing tools for modular construction of modal logics admitting disjunctive bases. Finally, we consider the problem of giving a category-theoretic formulation of disjunctive bases, and provide a partial solution.
Assessing the Performance of Leja and Clenshaw-Curtis Collocation for Computational Electromagnetics with Random Input Data
Venue: arXiv cs.CE 2022
Year: 2022

We consider the problem of quantifying uncertainty regarding the output of an electromagnetic field problem in the presence of a large number of uncertain input parameters. In order to reduce the growth in complexity with the number of dimensions, we employ a dimension-adaptive stochastic collocation method based on nested univariate nodes. We examine the accuracy and performance of collocation schemes based on Clenshaw-Curtis and Leja rules, for the cases of uniform and bounded, non-uniform random inputs, respectively. Based on numerical experiments with an academic electromagnetic field model, we compare the two rules in both the univariate and multivariate case and for both quadrature and interpolation purposes. Results for a real-world electromagnetic field application featuring high-dimensional input uncertainty are also presented.
Convolutional Neural Networks combined with Runge-Kutta Methods
Venue: arXiv cs.CV 2022
Year: 2022

A convolutional neural network can be constructed using numerical methods for solving dynamical systems, since the forward pass of the network can be regarded as a trajectory of a dynamical system. However, existing models based on numerical solvers cannot avoid the iterations of implicit methods, which makes the models inefficient at inference time. In this paper, we reinterpret the pre-activation Residual Networks (ResNets) and their variants from the dynamical systems view. We consider that the iterations of implicit Runge-Kutta methods are fused into the training of these models. Moreover, we propose a novel approach to constructing network models based on high-order Runge-Kutta methods in order to achieve higher efficiency. Our proposed models are referred to as the Runge-Kutta Convolutional Neural Networks (RKCNNs). The RKCNNs are evaluated on multiple benchmark datasets. The experimental results show that RKCNNs are vastly superior to other dynamical system network models: they achieve higher accuracy with much fewer resources. They also expand the family of network models based on numerical methods for dynamical systems.
A Finite-Model-Theoretic View on Propositional Proof Complexity
Venue: arXiv cs.LO 2022
Year: 2022

We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional proof systems, such as Horn resolution, bounded-width resolution, and the monomial calculus of bounded degree, can be characterised in a precise sense by variants of fixed-point logics that are of fundamental importance in descriptive complexity theory. Our main results are that Horn resolution has the same expressive power as least fixed-point logic, that bounded-width resolution captures existential least fixed-point logic, and that the polynomial calculus with bounded degree over the rationals solves precisely the problems definable in fixed-point logic with counting. We also study the bounded-degree polynomial calculus. Over the rationals, it captures fixed-point logic with counting if we restrict the bit-complexity of the coefficients. For unrestricted coefficients, we can only say that the bounded-degree polynomial calculus is at most as powerful as bounded variable infinitary counting logic, but a precise logical characterisation of its power remains an open problem. These connections between logics and proof systems allow us to establish finite-model-theoretic tools for proving lower bounds for the polynomial calculus over the rationals and also over finite fields. This is a corrected version of the paper (arXiv:1802.09377) published originally on January 23, 2019.
Higher order monotonicity and submodularity of influence in social networks: from local to global
Venue: arXiv cs.SI 2022
Year: 2022

Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function $σ(S)$ is monotone and submodular, where $S$ is a seed set and the spread function $σ(S)$ denotes the expected number of active nodes at termination of a diffusion process starting from $S$. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD-k (Alternating Difference-$k$) as a generalization of monotonicity and submodularity. Specifically, a set function $f$ is called \adk if all the $\ell$-th order differences of $f$ on all inputs have sign $(-1)^{\ell+1}$ for every $\ell\leq k$. Note that AD-1 corresponds to monotonicity and AD-2 corresponds to monotonicity and submodularity. We propose a refined version of KKT's conjecture: in the general threshold model, local AD-k implies global AD-k. The original KKT conjecture corresponds to the case for AD-2, and the case for AD-1 is the trivial one of local monotonicity implying global monotonicity. By utilizing continuous extensions of set functions as well as social graph constructions, we prove the correctness of our conjecture when the social graph is a directed acyclic graph (DAG). Furthermore, we affirm our conjecture on general social graphs when $k=\infty$.