Search

Invariant norms, also called Barabanov norms, are defined in $R^d$ for any compact family $\mathcal A$ of $d \times d$ matrices. They correspond to the linear switching system, which is a differential equation $\dot x(t) = A(t)x(t)$, where $A(t) \in \mathcal A$ for each $t$. The invariant norm identifies the trajectories $x(t)$ of the fastest asymptotic growth as $t\to +\infty$. It also solves the stability problem. This norm is difficult to construct even for a pair of matrices. We show that in case $d=2$ the invariant norm can be found explicitly for every compact matrix family $\mathcal A$. If $\mathcal A$ does not contain a dominant matrix with a real spectrum, then this norm is always unique (up to a multiplier) and is $C^1$, otherwise, there may be infinitely many norms. All of them can be found and classified.

An antinorm is a concave analogue of a norm. In contrast to norms, antinorms are not defined on the entire space $R^d$ but on a cone $K\subset R^d$. They are applied in the matrix analysis, optimal control, and dynamical systems. Their level sets are called conic bodies and (in case of piecewise-linear antinorms) conic polyhedra. The basic facts and notions of the "concave analysis" of antinorms such as separation theorems, duality, polars, Minkowski functionals, etc., are similar to those from the standard convex analysis. There are, however, some significant differences. One of them is the existence of many self-dual objects. We prove that there are infinitely many families of autopolar conic bodies and polyhedra in the cone $K=R^d_+$. For $d=2$, this gives a complete classification of self-dual antinorms, while for $d\ge 3$, there are counterexamples.

Methods of computational quantum chemistry provide accurate approximations of molecular properties crucial for computer-aided drug discovery and other areas of chemical science. However, high computational complexity limits the scalability of their applications. Neural network potentials (NNPs) are a promising alternative to quantum chemistry methods, but they require large and diverse datasets for training. This work presents a new dataset and benchmark called $\nabla^2$DFT that is based on the nablaDFT. It contains twice as much molecular structures, three times more conformations, new data types and tasks, and state-of-the-art models. The dataset includes energies, forces, 17 molecular properties, Hamiltonian and overlap matrices, and a wavefunction object. All calculations were performed at the DFT level ($\omega$B97X-D/def2-SVP) for each conformation. Moreover, $\nabla^2$DFT is the first dataset that contains relaxation trajectories for a substantial number of drug-like molecules. We also introduce a novel benchmark for evaluating NNPs in molecular property prediction, Hamiltonian prediction, and conformational optimization tasks. Finally, we propose an extendable framework for training NNPs and implement 10 models within it., Comment: Published as a conference paper at NeurIPS2024 Track on Datasets and Benchmarks (Poster)

The problem considered first by I. Newton (1687) consists in finding a surface of the minimal frontal resistance in a parallel flow of non-interacting point particles. The standard formulation assumes that the surface is convex with a given convex base $\Omega$ and a bounded altitude. Newton found the solution for surfaces of revolution. Without this assumption the problem is still unsolved, although many important results have been obtained in the last decades. We consider the problem to characterize the domains $\Omega$ for which the flat surface gives a local minimum. We show that this problem can be reduced to an inequality between $L_2$-norms of partial derivatives for bivariate concave functions on a convex domain that vanish on the boundary. Can the ratio between those norms be arbitrarily large? The answer depends on the geometry of the domain. A complete criterion is derived, which also solves the local minimality problem., Comment: 17 pages, 6 figures

We address the problem of the best uniform approximation of a continuous function on a convex domain. The approximation is by linear combinations of a finite system of functions (not necessarily Chebyshev) under arbitrary linear constraints. By modifying the concept of alternance and of the Remez iterative procedure we present a method, which demonstrates its efficiency in numerical problems. The linear rate of convergence is proved under some favourable assumptions. A special attention is paid to systems of complex exponents, Gaussian functions, lacunar algebraic and trigonometric polynomials. Applications to signal processing, linear ODE, switching dynamical systems, and to Markov-Bernstein type inequalities are considered.

We decide the stability and compute the Lyapunov exponent of continuous-time linear switching systems with a guaranteed dwell time. The main result asserts that the discretization method with step size~$h$ approximates the Lyapunov exponent with the precision~$C\,h^2$, where~$C$ is a constant. Let us stress that without the dwell time assumption, the approximation rate is known to be linear in~$h$. Moreover, for every system, the constant~$C$ can be explicitly evaluated. In turn, the discretized system can be treated by computing the Markovian joint spectral radius of a certain system on a graph. This gives the value of the Lyapunov exponent with a high accuracy. The method is efficient for dimensions up to, approximately, ten; for positive systems, the dimensions can be much higher, up to several hundreds.

We consider the problem of partitioning a two-dimensional flat torus $T^2$ into $m$ sets in order to minimize the maximal diameter of a part. For $m \leqslant 25$ we give numerical estimates for the maximal diameter $d_m(T^2)$ at which the partition exists. Several approaches are proposed to obtain such estimates. In particular, we use the search for mesh partitions via the SAT solver, the global optimization approach for polygonal partitions, and the optimization of periodic hexagonal tilings. For $m=3$, the exact estimate is proved using elementary topological reasoning., Comment: 18 pages, 8 figures

The regularity of refinable functions has been analysed in an extensive literature and is well-understood in two cases: 1) univariate 2) multivariate with an isotropic dilation matrix. The general (non-isotropic) case offered a great resistance. It was done only recently by developing the matrix method. In this paper we make the next step and extend the Littlewood-Paley type method, which is very efficient in the aforementioned special cases, to general equations with arbitrary dilation matrices. This gives formulas for the higher order regularity in $W_2^k(\mathbb{R}^n)$ by means of the Perron eigenvalue of a finite-dimensional linear operator on a special cone. Applying those results to recently introduced tile B-splines, we prove that they can have a higher smoothness than the classical ones of the same order. Moreover, the two-digit tile B-splines have the minimal support of the mask among all refinable functions of the same order of approximation. This proves, in particular, the lowest algorithmic complexity of the corresponding subdivision schemes. Examples and numerical results are provided.

It is well-known that every isosceles tetrahedron (disphenoid) admits infinitely many simple closed geodesics on its surface. They can be naturally enumerated by pairs of co-prime integers $n > m > 1$ with two additional cases $(1,0)$ and $(1,1)$. The (n,m)-geodesic is a broken line with $4(n+m)$ vertices, its length tends to infinity as $m\to \infty$. Are there other polyhedra possessing this property? The answer depends on convexity. We give an elementary proof that among convex polyhedra only disphenoids admit arbitrarily long closed simple geodesics. For non-convex polyhedra, this is not true. We present a counterexample with the corresponding polyhedron being a union of seven equal cubes. Several open problems are formulated

If a linear switching system with frequent switches is stable, will it be stable under arbitrary switches? In general, the answer is negative. Nevertheless, this question can be answered in an explicit form for any concrete system. This is done by finding the mode-dependent critical lengths of switching intervals after which any enlargement does not influence the stability. The solution is given in terms of the exponential polynomials of least deviation from zero on a segment (``Chebyshev-like'' polynomials). By proving several theoretical results on exponential polynomial approximation we derive an algorithm for finding such polynomials and for computing the critical switching time. The convergence of the algorithm is estimated and numerical results are provided.

In recent years, computer vision has transformed fields such as medical imaging, object recognition, and geospatial analytics. One of the fundamental tasks in computer vision is semantic image segmentation, which is vital for precise object delineation. Autonomous driving represents one of the key areas where computer vision algorithms are applied. The task of road surface segmentation is crucial in self-driving systems, but it requires a labor-intensive annotation process in several data domains. The work described in this paper aims to improve the efficiency of image segmentation using a convolutional neural network in a multi-sensor setup. This approach leverages lidar (Light Detection and Ranging) annotations to directly train image segmentation models on RGB images. Lidar supplements the images by emitting laser pulses and measuring reflections to provide depth information. However, lidar's sparse point clouds often create difficulties for accurate object segmentation. Segmentation of point clouds requires time-consuming preliminary data preparation and a large amount of computational resources. The key innovation of our approach is the masked loss, addressing sparse ground-truth masks from point clouds. By calculating loss exclusively where lidar points exist, the model learns road segmentation on images by using lidar points as ground truth. This approach allows for blending of different ground-truth data types during model training. Experimental validation of the approach on benchmark datasets shows comparable performance to a high-quality image segmentation model. Incorporating lidar reduces the load on annotations and enables training of image-segmentation models without loss of segmentation quality. The methodology is tested on diverse datasets, both publicly available and proprietary. The strengths and weaknesses of the proposed method are also discussed in the paper., Comment: Preprint, 11 pages

Large language models (LLMs) have been shown to be able to perform new tasks based on a few demonstrations or natural language instructions. While these capabilities have led to widespread adoption, most LLMs are developed by resource-rich organizations and are frequently kept from the public. As a step towards democratizing this powerful technology, we present BLOOM, a 176B-parameter open-access language model designed and built thanks to a collaboration of hundreds of researchers. BLOOM is a decoder-only Transformer language model that was trained on the ROOTS corpus, a dataset comprising hundreds of sources in 46 natural and 13 programming languages (59 in total). We find that BLOOM achieves competitive performance on a wide variety of benchmarks, with stronger results after undergoing multitask prompted finetuning. To facilitate future research and applications using LLMs, we publicly release our models and code under the Responsible AI License.

Linguistic analysis of language models is one of the ways to explain and describe their reasoning, weaknesses, and limitations. In the probing part of the model interpretability research, studies concern individual languages as well as individual linguistic structures. The question arises: are the detected regularities linguistically coherent, or on the contrary, do they dissonate at the typological scale? Moreover, the majority of studies address the inherent set of languages and linguistic structures, leaving the actual typological diversity knowledge out of scope. In this paper, we present and apply the GUI-assisted framework allowing us to easily probe a massive number of languages for all the morphosyntactic features present in the Universal Dependencies data. We show that reflecting the anglo-centric trend in NLP over the past years, most of the regularities revealed in the mBERT model are typical for the western-European languages. Our framework can be integrated with the existing probing toolboxes, model cards, and leaderboards, allowing practitioners to use and share their standard probing methods to interpret multilingual models. Thus we propose a toolkit to systematize the multilingual flaws in multilingual models, providing a reproducible experimental setup for 104 languages and 80 morphosyntactic features. https://github.com/AIRI-Institute/Probing_framework, Comment: Accepted to BlackBoxNLP, EMNLP 2022

Quantitative estimates related to the classical Borsuk problem of splitting set in Euclidean space into subsets of smaller diameter are considered. For a given $k$ there is a minimal diameter of subsets at which there exists a covering with $k$ subsets of any planar set of unit diameter. In order to find an upper estimate of the minimal diameter we propose an algorithm for finding sub-optimal partitions. In the cases $10 \leqslant k \leqslant 17$ some upper and lower estimates of the minimal diameter are improved. Another result is that any set $M \subset \mathbb{R}^3$ of a unit diameter can be partitioned into four subsets of a diameter not greater than $0.966$., Comment: 19 pages, 17 figures

The Markov-Bernstein type inequalities between the norms of functions and of their derivatives are analysed for complex exponential polynomials. We establish a relation between the sharp constants in those inequalities and the stability problem for linear switching systems. In particular, the maximal discretization step is estimated. We prove the monotonicity of the sharp constants with respect to the exponents, provided those exponents are real. This gives asymptotically tight uniform bounds and the general form of the extremal polynomial. The case of complex exponent is left as an open problem.

The linear switching system is a system of ODE with the time-dependent matrix taking values from a given control matrix set. The system is (asymptotically) stable if all its trajectories tend to zero for every control function. We consider possible mode-dependent restrictions on the lengths of switching intervals which keeps the stability of the system. When the stability of trajectories with short switching intervals implies the stability of all trajectories? To answer this question we introduce the concept of "cut tail points" of linear operators and study them by the convex analysis tools. We reduce the problem to the construction of Chebyshev-type exponential polynomials, for which we derive an algorithm and present the corresponding numerical results.

One of the crucial tasks in computer science is the processing time reduction of various data types, i.e., images, which is important for different fields -- from medicine and logistics to virtual shopping. Compared to classical computers, quantum computers are capable of parallel data processing, which reduces the data processing time. This quality of quantum computers inspired intensive research of the potential of quantum technologies applicability to real-life tasks. Some progress has already revealed on a smaller volumes of the input data. In this research effort, I aimed to increase the amount of input data (I used images from 2 x 2 to 8 x 8), while reducing the processing time, by way of skipping intermediate measurement steps. The hypothesis was that, for increased input data, the omitting of intermediate measurement steps after each quantum convolution layer will improve output metric results and accelerate data processing. To test the hypothesis, I performed experiments to chose the best activation function and its derivative in each network. The hypothesis was partly confirmed in terms of output mean squared error (MSE) -- it dropped from 0.25 in the result of classical convolutional neural network (CNN) training to 0.23 in the result of quantum convolutional neural network (QCNN) training. In terms of the training time, however, which was 1.5 minutes for CNN and 4 hours 37 minutes in the least lengthy training iteration, the hypothesis was rejected., Comment: 11 pages (without references), 13 figures

We address the stability problem for linear switching systems with mode-dependent restrictions on the switching intervals. Their lengths can be bounded as from below (the guaranteed dwell-time) as from above. The upper bounds make this problem quite different from the classical case: a stable system can consist of unstable matrices, it may not possess Lyapunov functions, etc. We introduce the concept of Lyapunov multifunction with discrete monotonicity, which gives upper bounds for the Lyapunov exponent. Its existence as well as the existence of invariant norms are proved. Tight lower bounds are obtained in terms of a modified Berger-Wang formula over periodizable switching laws. Based on those results we develop a method of computation of the Lyapunov exponent with an arbitrary precision and analyse its efficiency in numerical results. The case when some of upper bounds can be cancelled is analysed.

The bouncing neutron is one of the rare system where gravity can be studied in a quantum framework. To this end it is crucial to be able to select some specific gravitational quantum state (GQS). The GRANIT apparatus is the first physics experiment connected to a superthermal helium UCN source. We report on the methods developed for this instrument showing how specific GQS can be favored using a step between mirrors and an absorbing slit. We explore the increase of GQS separation efficiency by increasing the absorber roughness amplitude, and find it is feasible but requires a high adjustment precision. We also quantify the transmission of the absorbing slit leading to a measurement of the spatial extension of the neutron vertical wave function $z_0 = \hbar^{2/3}\left(2m^2g\right)^{-1/3} = 5.9\pm0.3\,\mu$m., Comment: 5 pages, 3 figures

Literary texts are usually rich in meanings and their interpretation complicates corpus studies and automatic processing. There have been several attempts to create collections of literary texts with annotation of literary elements like the author's speech, characters, events, scenes etc. However, they resulted in small collections and standalone rules for annotation. The present article describes an experiment on lexical annotation of text worlds in a literary work and quantitative methods of their comparison. The experiment shows that for a well-agreed tag assignment annotation rules should be set much more strictly. However, if borders between text worlds and other elements are the result of a subjective interpretation, they should be modeled as fuzzy entities., Comment: Conference: Computational Linguistics and Intellectual Technologies. Papers from the Annual International Conference Dialogue At: Moscow, Russia Volume: Issue 18. Supplementary volume