14,990 research outputs found
The Yakubovich S-Lemma Revisited: Stability and Contractivity in Non-Euclidean Norms
No full textThe celebrated S-Lemma was originally proposed to ensure the existence of a
quadratic Lyapunov function in the Lur'e problem of absolute stability. A
quadratic Lyapunov function is, however, nothing else than a squared Euclidean
norm on the state space (that is, a norm induced by an inner product). A
natural question arises as to whether squared non-Euclidean norms
may serve as Lyapunov functions in stability problems. This
paper presents a novel non-polynomial S-Lemma that leads to constructive
criteria for the existence of such functions defined by weighted
norms. Our generalized S-Lemma leads to new absolute stability and absolute
contractivity criteria for Lur'e-type systems, including, for example, a new
simple proof of the Aizerman and Kalman conjectures for positive Lur'e systems
Non-Euclidean Contractivity of Recurrent Neural Networks
No full textCritical questions in dynamical neuroscience and machine learning are related to the study of recurrent neural networks and their stability, robustness, and computational efficiency. These properties can be simultaneously established via a contraction analysis.This paper develops a comprehensive contraction theory for recurrent neural networks. First, for non-Euclidean l 1 /l ∞ logarithmic norms, we establish quasiconvexity with respect to positive diagonal weights and closed-form worst-case expressions over certain matrix polytopes. Second, for locally Lipschitz maps (e.g., arising as activation functions), we show that their one-sided Lipschitz constant equals the essential supremum of the logarithmic norm of their Jacobian. Third and final, we apply these general results to classes of recurrent neural circuits, including Hopfield, firing rate, Persidskii, Lur’e and other models. For each model, we compute the optimal contraction rate and corresponding weighted non-Euclidean norm via a linear program or, in some special cases, via a Hurwitz condition on the Metzler majorant of the synaptic matrix. Our non-Euclidean analysis establishes also absolute, connective, and total contraction properties
New bounds for linear codes of covering radius 3 and 2-saturating sets in projective spaces
No full textThe length function l_q(r,R) is the smallest length of a q-ary linear code of covering radius R and codimension (redundancy) r. In this paper, we obtained new upper bounds on l_q(r,3), r = 3t+1 ≥ 4, and r = 3t+2 ≥ 5, t ≥ 1. For r = 4,5 we usetheone-to-one correspondence between [n,n−r]qR codesand (R−1)-saturating sets (e.g. complete arcs) in the projective space PG(r−1,q).Then,with the help of lift-constructions increasing r, we obtain new upper bounds on l_q(3t + 1,3), l_q(3t + 2,3).
Also, in PG(3,q) we consider an iterative step-by-step construction of complete arcs and prove that uncovered points are evenly placed on the space. A natural conjecture on an estimate of the number of new covered points in every step is done. Under this conjecture, the following bounds for values of q, not limited from above, are proposed:
l_q(r,3) < 3 (ln q)^(1/3)·q^((r−3)/3), r = 3t + 1 ≥ 4, t ≥ 1
Further Results on Orbits and Incidence Matrices for the Class O_6 of Lines External to the Twisted Cubic in PG(3,q)
No full textIn the literature, lines of the projective space PG(3,q) are partitioned into classes, each of which is a union of line orbits under the stabilizer group of the twisted cubic. The least studied class is named O_6. This class contains lines external to the twisted cubic which are not its chords or axes and do not lie in any of its osculating planes. For even and odd q, we propose a new family of orbits of O_6 and investigate in detail their stabilizer groups and the corresponding submatrices of the point-line and plane-line incidence matrices. To obtain these submatrices, we explored the number of solutions of cubic and quartic equations connected with intersections of lines (including the tangents to the twisted cubic), points, and planes in PG(3,q)
Non-Euclidean Contraction Analysis of Continuous-Time Neural Networks
No full textCritical questions in dynamical neuroscience and machine learning are related to the study of continuous-time neural networks and their stability, robustness, and computational efficiency. These properties can be simultaneously established via a contraction analysis. This paper develops a comprehensive non-Euclidean contraction theory for continuous-time neural networks. Specifically, we provide novel sufficient conditions for the contractivity of general classes of continuous-time neural networks including Hopfield, firing rate, Persidskii, Lur'e, and other neural networks with respect to the non-Euclidean norms. These sufficient conditions are based upon linear programming or, in some special cases, establishing the Hurwitzness of a particular Metzler matrix. To prove these sufficient conditions, we develop novel results on non-Euclidean logarithmic norms and a novel necessary and sufficient condition for contractivity of systems with locally Lipschitz dynamics. For each model, we apply our theoretical results to compute the optimal contraction rate and corresponding weighted non-Euclidean norm with respect to which the neural network is contracting
Euclidean Contractivity of Neural Networks with Symmetric Weights
No full textThis paper investigates stability conditions of continuous-time Hopfield and
firing-rate neural networks by leveraging contraction theory. First, we present
a number of useful general algebraic results on matrix polytopes and products
of symmetric matrices. Then, we give sufficient conditions for strong and weak
Euclidean contractivity, i.e., contractivity with respect to the norm,
of both models with symmetric weights and (possibly) non-smooth activation
functions. Our contraction analysis leads to contraction rates which are
log-optimal in almost all symmetric synaptic matrices. Finally, we use our
results to propose a firing-rate neural network model to solve a quadratic
optimization problem with box constraints.Comment: 17 pages, 2 figure
Douglas Alexander Stewart, poet, author and playwright
No full textDouglas Alexander Stewart, poet, author and playwrigh
Non-Euclidean Monotone Operator Theory and Applications
No full textWhile monotone operator theory is often studied on Hilbert spaces, many interesting
problems in machine learning and optimization arise naturally in finite-dimensional vector spaces endowed with non-Euclidean norms, such as diagonally-weighted `1 or `∞
norms. This paper provides a natural generalization of monotone operator theory to finitedimensional non-Euclidean spaces. The key tools are weak pairings and logarithmic norms.
We show that the resolvent and reflected resolvent operators of non-Euclidean monotone
mappings exhibit similar properties to their counterparts in Hilbert spaces. Furthermore,
classical iterative methods and splitting methods for finding zeros of monotone operators
are shown to converge in the non-Euclidean case. We apply our theory to equilibrium computation and Lipschitz constant estimation of recurrent neural networks, obtaining novel
iterations and tighter upper bounds via forward-backward splittin
On Weakly Contracting Dynamics for Convex Optimization
No full textWe analyze the convergence behavior of globally weakly and locally strongly contracting dynamics. Such dynamics naturally arise in the context of convex optimization problems with a unique minimizer. We show that convergence to the equilibrium is linear-exponential, in the sense that the distance between each solution and the equilibrium is upper bounded by a function that first decreases linearly and then exponentially. As we show, the linear-exponential dependency arises naturally in certain dynamics with saturations. Additionally, we provide a sufficient condition for local input-to-state stability. Finally, we illustrate our results on, and propose a conjecture for, continuous-time dynamical systems solving linear programs
Positive Competitive Networks for Sparse Reconstruction
No full text: We propose and analyze a continuous-time firing-rate neural network, the positive firing-rate competitive network (PFCN), to tackle sparse reconstruction problems with non-negativity constraints. These problems, which involve approximating a given input stimulus from a dictionary using a set of sparse (active) neurons, play a key role in a wide range of domains, including, for example, neuroscience, signal processing, and machine learning. First, by leveraging the theory of proximal operators, we relate the equilibria of a family of continuous-time firing-rate neural networks to the optimal solutions of sparse reconstruction problems. Then we prove that the PFCN is a positive system and give rigorous conditions for the convergence to the equilibrium. Specifically, we show that the convergence depends only on a property of the dictionary and is linear-exponential in the sense that initially, the convergence rate is at worst linear and then, after a transient, becomes exponential. We also prove a number of technical results to assess the contractivity properties of the neural dynamics of interest. Our analysis leverages contraction theory to characterize the behavior of a family of firing-rate competitive networks for sparse reconstruction with and without non-negativity constraints. Finally, we validate the effectiveness of our approach via a numerical example
- …
