ABSTRACT The algebraic connectivity is an indicator of how well connected a graph is. It also characterizes the convergence speed of some dynamic processes over networks. In this paper, taking into account that homogeneous networks are modeled as regular graphs, we tackle the following problem: given a pair of positive integers such that is less than and is an even number, find a ‐regular graph with vertices that have the maximum algebraic connectivity. We first consider some special cases and derive solutions through theoretical analysis. We next present depth‐first search algorithms for solving the problem, which reduce the search space by making use of some known properties of the regular graph and the algebraic connectivity. We also show the results of execution of the proposed algorithms for the values of up to .

A recurrent neural network (RNN) can generate a sequence of patterns as the temporal evolution of the output vector. This paper focuses on a continuous-time RNN model with a piecewise-linear activation function that has neither external inputs nor hidden neurons, and studies the problem of finding the parameters of the model so that it generates a given sequence of bipolar vectors. First, a sufficient condition for the model to generate the desired sequence is derived, which is expressed as a system of linear inequalities in the parameters. Next, three approaches to finding solutions of the system of linear inequalities are proposed: One is formulated as a convex quadratic programming problem and others are linear programming problems. Then, two types of sequences of bipolar vectors that can be generated by the model are presented. Finally, the case where the model generates a periodic sequence of bipolar vectors is considered, and a sufficient condition for the trajectory of the state vector to converge to a limit cycle is provided.

Abstract Nonnegative Matrix Factorization (NMF) has attracted a great deal of attention as an effective technique for dimensionality reduction of large-scale nonnegative data. Given a nonnegative matrix, NMF aims to obtain two low-rank nonnegative factor matrices by solving a constrained optimization problem. The Hierarchical Alternating Least Squares (HALS) algorithm is a well-known and widely-used iterative method for solving such optimization problems. However, the original update rule used in the HALS algorithm is not well defined. In this paper, we propose a novel well-defined update rule of the HALS algorithm, and prove its global convergence in the sense of Zangwill. Unlike conventional globally-convergent update rules, the proposed one allows variables to take the value of zero and hence can obtain sparse factor matrices. We also present two stopping conditions that guarantee the finite termination of the HALS algorithm. The practical usefulness of the proposed update rule is shown through experiments using real-world datasets.

Computer networks in data centers are often modeled by undirected regular graphs, and the average shortest path length (ASPL) of the graph is closely related to the data transmission latency. Therefore, finding an undirected regular graph with the minimum ASPL is an important problem for building a low latency network. An undirected regular graph is called a generalized Moore graph (GMG) when its ASPL is identical with the theoretical lower bound. Several methods have been proposed so far to find GMGs with given order and degree. However, they do not make a full use of the properties of GMGs. In this paper, we propose some efficient algorithms for finding a GMG and examine their effectiveness by experiments.

Recently a sufficient condition for the recurrent neural network with the piecewise-linear output characteristic to generate a prescribed periodic sequence of binary vectors such that every two consecutive vectors differ in exactly one component has been derived. If a recurrent neural network satisfies this condition, it is guaranteed that any state trajectory of the network passes through the periodic sequence of regions corresponding to the periodic sequence of binary vectors. However, the asymptotic behavior of the state trajectories has not been clarified yet. In this paper, we study asymptotic behavior of state trajectories of recurrent neural networks satisfying the above-mentioned sufficient condition, and derive a criterion for state trajectories to converge a unique limit cycle.

Global convergence of the sequential minimal optimization (SMO) algorithm for support vector regression (SVR) is studied in this paper. Given l training samples, SVR is formulated as a convex quadratic programming (QP) problem with l pairs of variables. We prove that if two pairs of variables violating the optimality condition are chosen for update in each step and subproblems are solved in a certain way, then the SMO algorithm always stops within a finite number of iterations after finding an optimal solution. Also, efficient implementation techniques for the SMO algorithm are presented and compared experimentally with other SMO algorithms.

Connected component detection (CCD) is an important image processing task done by one-dimensional cellular neural networks (1-D CNNs). Recently, some sufficient conditions for 1-D CNNs with the antisymmetric template A = [s,p, -s] to perform CCD have been derived under the assumption that the outputs of the boundary cells are set to 1 or -1. In this paper, we extend these results to 1-D CNNs with the opposite-sign template A = [r,p, -s]. It is shown that the 1-D CNN can perform CCD for a wide range of parameter space. Therefore we can design 1-D CNNs which not only can perform CCD but also are robust against small perturbations of the parameters.

A sequential minimal optimization (SMO) algorithm for support vector regression (SVR) has recently been proposed by Flake and Lawrence. However, the convergence of their algorithm has not been proved so far. In this paper, we consider an SMO algorithm, which deals with the same optimization problem as Flake and Lawrence's SMO, and give a rigorous proof that it always stops within a finite number of iterations.

Global dynamical behavior of one-dimensional cellular neural networks (1D CNNs) with the antisymmetric template A = [s,p, -s] is studied in this paper. Under the assumption that the outputs of the boundary cells are fixed to 1 or -1, a new sufficient condition for such CNNs to perform connected component detection will be presented

Decomposition methods are well-known techniques for solving quadratic programming (QP) problems arising in support vector machines (SVMs). In each iteration of a decomposition method, a small number of variables are selected and a QP problem with only the selected variables is solved. Since large matrix computations are not required, decomposition methods are applicable to large QP problems. In this paper, we will make a rigorous analysis of the global convergence of general decomposition methods for SVMs. We first introduce a relaxed version of the optimality condition for the QP problems and then prove that a decomposition method reaches a solution satisfying this relaxed optimality condition within a finite number of iterations under a very mild condition on how to select variables.

Sequential minimal optimization (SMO) algorithm is one of the simplest decomposition methods for learning of support vector machines (SVMs). Keerthi and Gilbert have recently studied the convergence property of SMO algorithm and given a proof that SMO algorithm always stops within a finite number of iterations. In this letter, we point out the incompleteness of their proof and give a more rigorous proof.

A Boolean technology mapping with permissible functions is presented. This technique makes use of complementary intermediate logic functions of circuits. Therefore, complementary outputs of ECL gates can be easily handled. High-quality synthesized ECL circuits and CMOS circuits free of logical redundancies are generated. Technology-independent networks are converted into technology-dependent virtual gates network. Virtual gates have an arbitrary number of fan-ins. CMOS virtual networks consist of only NOR and NAND gates, while ECL virtual networks consist of only OR gates (but each gate has complementary outputs). By considering logic function and the device restrictions these virtual gate networks are translated into cell networks using permissible functions.>