RANDOMIZED KACZMARZ ALGORITHMS: EXACT MSE ANALYSIS AND OPTIMAL SAMPLING PROBABILITIES

	RANDOMIZED KACZMARZ ALGORITHMS: EXACT MSE ANALYSIS AND OPTIMAL SAMPLING PROBABILITIES
	Agaskar, A 4; Wang, C 1,3; Lu, YM
	2014
会议日期	DEC 03-05, 2014
会议地点	Atlanta, GA
关键词	ALGEBRAIC RECONSTRUCTION TECHNIQUES
页码	389-393
英文摘要	The Kaczmarz method, or the algebraic reconstruction technique (ART), is a popular method for solving large-scale overdetermined systems of equations. Recently, Strohmer et al. proposed the randomized Kaczmarz algorithm, an improvement that guarantees exponential convergence to the solution. This has spurred much interest in the algorithm and its extensions. We provide in this paper an exact formula for the mean squared error (MSE) in the value reconstructed by the algorithm. We also compute the exponential decay rate of the MSE, which we call the "annealed" error exponent. We show that the typical performance of the algorithm is far better than the average performance. We define the "quenched" error exponent to characterize the typical performance. This is far harder to compute than the annealed error exponent, but we provide an approximation that matches empirical results. We also explore optimizing the algorithm's row-selection probabilities to speed up the algorithm's convergence.
会议录	2014 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP)
会议录出版者	IEEE
会议录出版地	NEW YORK
语种	英语
ISBN号	978-1-4799-7088-9
WOS研究方向	Computer Science ; Engineering
内容类型	会议论文
源URL	[http://ir.itp.ac.cn/handle/311006/23599]
专题	SCI会议论文
作者单位	1.MIT Lincoln Lab, Lexington, MA 02420 USA 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China 4.[Agaskar, Ameya; Lu, Yue M.] Harvard Univ, Cambridge, MA 02138 USA
推荐引用方式 GB/T 7714	Agaskar, A,Wang, C,Lu, YM. RANDOMIZED KACZMARZ ALGORITHMS: EXACT MSE ANALYSIS AND OPTIMAL SAMPLING PROBABILITIES[C]. 见:. Atlanta, GA. DEC 03-05, 2014.