TY - JOUR

T1 - Pairwise optimal weight realization - Acceleration technique for set-theoretic adaptive parallel subgradient projection algorithm

AU - Yukawa, Masahiro

AU - Yamada, Isao

N1 - Funding Information:
Manuscript received March 4, 2005; accepted January 23, 2006. This work was supported in part by JSPS under Grant-in-Aid C15500129. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Sergio Theodoridis. Preliminary short versions of this paper were partially introduced at the IFAC Workshop on Adaptation and Learning in Control and Signal Processing, Yokohama, Japan, August 30–September 1, 2004, and the Twelfth European Signal Processing Conf. (EUSIPCO), Vienna, Austria, September 6–10, 2004.

PY - 2006/12

Y1 - 2006/12

N2 - The adaptive parallel subgradient projection (PSP) algorithm was proposed in 2002 as a set-theoretic adaptive filtering algorithm providing fast and stable convergence, robustness against noise, and low computational complexity by using weighted parallel projections onto multiple time-varying closed half-spaces. In this paper, we present a novel weighting technique named pairwise optimal weight realization (POWER) for further acceleration of the adaptive PSP algorithm. A simple closed-form formula is derived to compute the projection onto the intersection of two closed half-spaces defined by a triplet of vectors. Using the formula inductively, the proposed weighting technique realizes a good direction of update. The resulting weights turn out to be pairwise optimal in a certain sense. The proposed algorithm has the inherently parallel structure composed of q primitive functions, hence its total computational complexity O(qrN) is reduced to O(rN) with q concurrent processors (r: a constant positive integer). Numerical examples demonstrate that the proposed technique for r =1 yields significantly faster convergence than not only adaptive PSP with uniform weights, affine projection algorithm, and fast Newton transversal filters but also the regularized recursive least squares algorithm.

AB - The adaptive parallel subgradient projection (PSP) algorithm was proposed in 2002 as a set-theoretic adaptive filtering algorithm providing fast and stable convergence, robustness against noise, and low computational complexity by using weighted parallel projections onto multiple time-varying closed half-spaces. In this paper, we present a novel weighting technique named pairwise optimal weight realization (POWER) for further acceleration of the adaptive PSP algorithm. A simple closed-form formula is derived to compute the projection onto the intersection of two closed half-spaces defined by a triplet of vectors. Using the formula inductively, the proposed weighting technique realizes a good direction of update. The resulting weights turn out to be pairwise optimal in a certain sense. The proposed algorithm has the inherently parallel structure composed of q primitive functions, hence its total computational complexity O(qrN) is reduced to O(rN) with q concurrent processors (r: a constant positive integer). Numerical examples demonstrate that the proposed technique for r =1 yields significantly faster convergence than not only adaptive PSP with uniform weights, affine projection algorithm, and fast Newton transversal filters but also the regularized recursive least squares algorithm.

KW - Adaptive parallel subgradient projection

KW - Optimal weight design

KW - Set-theoretic adaptive filtering

UR - http://www.scopus.com/inward/record.url?scp=33947144069&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33947144069&partnerID=8YFLogxK

U2 - 10.1109/TSP.2006.881225

DO - 10.1109/TSP.2006.881225

M3 - Article

AN - SCOPUS:33947144069

SN - 1053-587X

VL - 54

SP - 4557

EP - 4571

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 12

ER -