Adaptive Alternating Minimization Algorithms

被引：85

作者：

Niesen, Urs ^{[1
]}

Shah, Devavrat ^{[1
]}

Wornell, Gregory W. ^{[1
]}

机构：

[1] MIT, Dept Elect Engn & Comp Sci, Cambridge, MA 02139 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2009年 / 55卷 / 03期

基金：

美国国家科学基金会;

关键词：

Adaptive filters; adaptive signal processing; algorithms; Arimoto-Blahut algorithm; optimization methods; CAPACITY; DESIGN;

D O I：

10.1109/TIT.2008.2011442

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application in many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm are known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. More precisely, we consider the impact of having a slowly time-varying domain over which the minimization takes place. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps somewhat surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

引用

页码：1423 / 1429

页数：7

共 13 条

[1]

[Anonymous], 2004, INFORM THEORY STAT T

[2] ALGORITHM FOR COMPUTING CAPACITY OF ARBITRARY DISCRETE MEMORYLESS CHANNELS [J].

ARIMOTO, S .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1972, 18 (01) :14-+

[3] COMPUTATION OF CHANNEL CAPACITY AND RATE-DISTORTION FUNCTIONS [J].

BLAHUT, RE .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1972, 18 (04) :460-+

[4] Equiripple FIR filter design by the FFT algorithm [J].

Cetin, AE ;

Gerek, ON ;

Yardimci, Y .

IEEE SIGNAL PROCESSING MAGAZINE, 1997, 14 (02) :60-64

[5]

COMBETTES PL, 1993, P IEEE, V81, P182, DOI 10.1109/5.214546

[6] INCONSISTENT SIGNAL FEASIBILITY PROBLEMS - LEAST-SQUARES SOLUTIONS IN A PRODUCT SPACE [J].

COMBETTES, PL .

IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1994, 42 (11) :2955-2966

[7]

Cover T. M., 1984, IEEE Transactions on Information Theory, VIT-30, P369, DOI 10.1109/TIT.1984.1056869

[8]

Csiszar I., 1984, Statistics and Decisions, P205

[9] MAXIMUM LIKELIHOOD FROM INCOMPLETE DATA VIA EM ALGORITHM [J].

DEMPSTER, AP ;

LAIRD, NM ;

RUBIN, DB .

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-METHODOLOGICAL, 1977, 39 (01) :1-38

[10]

DeVore R.A., 1993, Constructive Approximation, volume 303 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]

← 1 2 →