CONTENTS

Compressive Sensing

Granichin O.N. (SPbSU) Randomized Measurements and l_1-optimization

Randomized Algorithms

Vakhitov A.T. (SPbSU) Non-stationary Stochastic Optimization with
Fixed Gain SPSA-type Algorithms in the Case of Infinite Variance of
Random Uncertainties

Gatchkov A. A. (SPbSU) Financial Market Data Randomized R/S-
analysis

Tikhomirov A.S. (Novgorod State University, Velikiy Novgorod) On
Fast Variants of the Simulated Annealing Algorithm

Shcherbakov P.S. (ICS RAS, Moscow) Generation of Stable Polynomials

Queuing Systems

Drac A.V., Sokolov A.V. (IAMR KarSC RAS, Petrozavodsk) The
Analysis of Some Queue with n Priorities Allocation Methods

Ponomareva A.Yu., Stroilov R.M., Tchirkov M.K. (SPbBU) Special Optimization Procedures for Periodically Nonstationary Stochastic Automata

Timonina A.V. (MIPT, Moscow) The Rank-Model and Its Investigations

Learning and Adaptation

Amelin K.S., Antal K.I., Vasiliev V.I., Granichina N.O. (SPbSU) Adaptive Control of Autonomous Group of Unmanned Aerial Vehicles

Granichina N. O., Shalymov D. S. (SPbSU) A Randomized Algorithm
of Cluster Stability

Hieu Le Trung (SPbSU) An Unsupervised Learning and Statistical Approach
for Vietnamese Word Recognition and Segmentation

Electric Power Systems

Misrikhanov M.Sh., Ryabchenko V.N. (METCC, Moskow) Iterative
Steady-state Stability Criterion of Power System Described by Algebro-
differential Equations

 

 

Compressive Sensing

 

Randomization of Measurements and l1-optimization

O. N. Granichin

St. Petersburg State University

Oleg_granichin@mail.ru

Key words: compressive sensing, compressive sampling, randomized measurements, l_1-optimization.

At present, the new coding/decoding paradigm named compressive sensing is being actively developed for signals having sparse representation in some basis. The underlying idea is randomization of measurement processes and l_1-optimization technique. The paper describes a new acquiring method of sparse signals and their representation using considerably less amount of data than in the classical representation with Nyquist rate.

Bibliogr.: 31 refs.

full text pdf

 

Randomized Algorithms

 

Non-stationary Stochastic Optimization with Fixed Gain SPSA-type Algorithms in the Case of Infinite Variance of Random Uncertainties

A. T. Vakhitov

St. Petersburg State University

av38@yandex.ru

Key words: non-stationary stochastic optimization, dynamic optimization, infinite variance, stochastic approximation, SPSA

In this paper, we formulate the problem of non-stationary stochastic optimization in the case of infinite variance of uncertainties. The three randomized stochastic approximation-type algorithms with fixed gain are proposed. The conditions of stabilization of the estimates are given and probabilistic bounds on the estimation error are presented.

Bibliogr.: 16 refs.

full text pdf

 

Financial Market Data Randomized R/S-analysis

A. A. Gatchkov

St. Petersburg State University

agachkov@mail.ru

Key words: R/S-analysis, financial data analysis, randomization.

At present, the fractal approach to the financial markets risks definition is rapidly developing. It proposes to use a fractal dimension of market asset prices as a measure of risk. The R/S-analysis algorithm is often used during the calculation of such fractal dimension. The algorithm works quite well for input data purified from noise. However, when a system is subjected to noise and deviations that may occur, for example, as a result of the impact of major market players during the speculative trade, the algorithm exposes a big error. The proposed randomized R/S-analysis algorithm allows to estimate risks more precisely in the case of systematic noise.

Bibliogr.: 13 refs.

full text pdf

 

On Fast Variants

of the Simulated Annealing Algorithm

A. S. Tikhomirov

Novgorod State University, Velikiy Novgorod

Tikhomirov.AS@mail.ru, TikhomirovAlesha@gmail.com

Key words: simulated annealing, random search, stochastic search, global optimization, stochastic optimization.

Fast versions of the simulated annealing algorithm are constructed. It is shown that the asymptotic rate of convergence of the simulated annealing algorithm may be just marginally worse than the rate of convergence of a standard descent algorithm (e.g., steepest descent).

Bibliorg.: 23 refs.

full text pdf

 

Generation of Stable Polynomials

P. S. Shcherbakov

Institute of Control Science, RAS, Moscow

sherba@ipu.ru

Key words: stable polynomials, randomization, random generation methods, parametrization, Matlab-realizations.

In this paper, various techniques for random generation of stable polynomials in discrete and continuous time are considered and presented in a unified framework. An attempt is made to present a global vision of the potentials of random generation techniques for stable polynomials. Moreover, their properties are discussed and compared, with a particular attention to the Matlab implementation issues. Possible applications are indicated and illustrative results of simulations are provided.

Bibliogr.: 34 refs.

full text pdf

 

Queuing Systems

 

The Analysis of Some Queue with n Priorities Allocation Methods

A. V. Drac, A. V. Sokolov

Petrozavodsk State University, IAMR KarSC RAS, Petrozavodsk

adeon88@mail.ru, avs@krc.karelia.ru

Key words: priority queue, FIFO-queues, Random walk, Markov chains, dynamical data structures.

This paper considers a representation of queues with n priorities in single-level memory in the form of array or as n consecutive FIFO queues. Possible operations are insert element, delete an element with maximum priority, and find element. Proposed are the algorithms of state enumeration, construction of appropriate absorbent Markov chains, and finding the optimal memory partition that maximizes the average time until memory overflow. The results of numerical experiments are presented.

Bibliorg.: 9 refs.

full text pdf

 

Special Optimization Procedures for Periodically Nonstationary Stochastic Automata

A. Yu. Ponomareva, R. M. Stroilov, M. K. Tchirkov

St. Petersburg State University

vakh@star.math.spbu.ru

Key words: periodically nonstationary stochastic automata, optimization of stochastic automata, inaccessible states, restricted initial conditions.

The paper deals with solution of some special optimization problems for nonstationary stochastic automaton with periodically variable structure. These problems are related to theoretical justification and development of certain procedures which optimize the number of states of such automata in various structural cycles with constrained initial conditions.

Bibliogr.: 6 refs.

full text pdf

 

The Rank-Model and Its Investigations

A. V. Timonina

Moscow Institute of Physics and Technology

timonina.ann@gmail.com

Key words: rank, stochastic matrix, eigenvector, PageRank, power method.

This paper presents analysis of a large-dimensional network exemplified by the Internet. The goal of the study is to develop an algorithm that correctly finds the PageRank of a web-page. The test model of the Internet is constructed that demonstrates the existence of a significant discrepancies between the exact value of the page-weight and the Page-Rank.

Bibliorg.: 8 refs.

full text pdf

 

Learning and Adaptation

 

Adaptive Control of Autonomous Group of Unmanned Aerial Vehicles

K. S Amelin.,K. I. Antal, V. I. Vasiliev, N. O. Granichina

St. Petersburg State University

konstantinamelin@mail.ru, cathrineantal@gmail.com, gnome@bk.ru,

ngranichina@mail.ru

Key words: multiagent systems, unmanned aerial vehicles, adaptive control, autonomous group of unmanned aerial vehicles.

In this paper, we discuss possible use of a multiagent system for adaptive control of a group of unmanned aerial vehicles (UAV). The system is based on independent dialogue of the agents through a radio signal. Adaptability will facilitate efficient on-line decision-making in changing the scenario of the goal attainment.

Bibliogr.: 6 refs.

full text pdf

 

A Randomized Algorithm of Cluster Stability

N. O. Granichina, D. S. Shalymov

St. Petersburg State University (ngranichina, shalydim)@mail.ru

Key words: clustering, cluster stability, randomized algorithms, randomized algorithms of cluster stability.

Clustering is the subject of active research in several fields such as statistics, pattern recognition, machine learning. etc. In this paper, the notion of clustering and cluster stability is introduced, the urgency and the basic problems of clustering are described. A new randomized algorithm of cluster stability is formulated and its convergence properties are proved.

Bibliogr.: 42 refs.

full text pdf

 

An Unsupervised Learning and Statistical Approach for Vietnamese Word Recognition and Segmentation

Le Trung Hieu

St. Petersburg State University

vkhhieukien@yahoo.com

Key words: Vietnamese word recognition, segmentation Vietnamese documents, unsupervised learning, statistical methods.

There are two main topics considered in this paper: (i) Vietnamese words are recognized and sentences are segmented into words by using probabilistic models; (ii) the optimum probabilistic model is constructed by an unsupervised learning iteration. For each probabilistic model, new words are recognized and their syllables are linked together. They are new syllables in a new probabilistic model. The syllable-linking process increases the accuracy of statistical functions resulting in a better recognition of the new words. This ensures the convergence of the probabilistic model to the optimal one.

Our experimented corpus is generated from about 250.034 online news articles, which consist of about 15 000 000 sentences. The accuracy of the segmented algorithm is over 90%. Our Vietnamese word and phrase dictionary contains more than 100 000 words and word combinations.

Bibliogr.: 15 refs.

full text pdf

 

 

Electric Power Systems

 

Iterative Steady-state Stability Criterion of Power System Described by Algebro-differential Equations

M. Sh. Misrikhanov, V. N. Ryabchenko,

Main electricity transmission company Center, Moskow

(mms, rvn)@mes-centra.ru

Key words: power system, algebro-differential form, steady-state stability, generalized matrix sign function, iterative algorithm.

A new iterative steady-state stability criterion of power system given by the algebro-differential equations is described. The core of the criterion is an iterative algorithm for computing the generalized matrix sign function. The problem of steady-state stability of UPS of Center model, described in the Cauchy form and by algebro-differential equations is solved.

Bibliogr.: 14 refs.

full text pdf