基于阵列码的准循环测量矩阵构造刘鑫吉1,2，夏树涛1,21清华大学深圳研究生院，深圳5180552清华大学计算机科学与技术系，北京100084摘要：近期，Dimakis，Smarandache和Vontobel指出在基追踪（BP）重建算法下，好的LDPC码校验矩阵常常是好的压缩感知测量矩阵。本文研究了一类重要的有结构LDPC码——阵列码（arraycodes）的校验矩阵H(r,q)。在压缩感知理论中，测量矩阵的spark定义为测量矩阵中线性相关的列的数目的最小值，它是一个重要的性能参数。本文给出了H(2,q)和H(3,q)的spark的精确值以及在r≥4时H(r,q)的spark的两个下界。进一步地，本文通过大量的仿真说明阵列码的校验矩阵及其子矩阵的性能常常优于高斯随机矩阵。基于阵列码构造的测量矩阵具有良好的准循环结构，非常方便硬件实现，有着巨大的应用潜力。关键词：压缩感知，低密度校验码，阵列码，测量矩阵，spark，准循环中图分类号：O236.2ConstructionsofQuasi-CyclicMeasurementMatricesBasedonArrayCodesLIUXin-Ji1,XIAShu-Tao1,21GraduateSchoolatShenzhen,TsinghuaUniversity,Shenzhen5180552DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084Abstract:Recently,Dimakis,Smarandache,andVontobelindicatedthattheparity-checkmatricesofgoodLDPCcodescanbeusedasprovablygoodmeasurementmatricesforcompressedsensing(CS)underbasispursuit(BP).Inthispaper,weconsidertheparity-checkmatrixH(r,q)ofthearraycodes,oneofthemostimportantkindofstructuredLDPCcodes.Thespark,i.e.thesmallestnumberoflinearlydependentcolumnsinamatrix,ofH(2,q)andH(3,q)aredeterminedandtwolowerboundsofthesparksofH(r,q)aregivenforr≥4.Moreover,wecarryoutnumbersofsimulationsandshowthatmanyparity-checkmatricesofarraycodesandtheirsubmatricesperformbetterthanthecorrespondingGaussianrandommatrices.Theproposedmeasurementmatriceshaveperfectquasi-cyclicstructuresandcanmakethehardwarerealizationconvenientandeasy,thushavinggreatpotentialsinpractice.Keywords:Compressedsensing,Low-densityparity-checkcodes(LDPC),arraycodes,measurementmatrix,spark,quasi-cyclic基金项目：TheResearchFundfortheDoctoralProgramofHigherEducationofChina(20100002110033)andtheMajorStateBasicResearchDevelopmentProgramofChina(973Program,2012CB315803).作者简介：LiuXin-Ji（1989-），male，PhDstudent，majorresearchdirection：compressedsensing,Email:li-uxj11@mails.tsinghua.edu.cn.Correspondenceauthor：XiaShu-Tao（1972-），male，professor，majorresearchdirection：error-correctingcodes,compressedsensing,networkcoding,Email:xiast@sz.tsinghua.edu.cn.-1-0IntroductionForak-sparsesignalx∈Rnwithatmostknonzerocomponents,compressedsensing(CS)[1,2]aimstorecoveringitfromitslinearmeasurementsy=Hx,whereH∈Rm×nisthemeasurementmatrixwithm≪n.Thiscanbedonebysolvingthefollowingl0-optimizationproblemmin||x||0s.t.Hx=y.(1)Unfortunately,itiswell-knownthattheproblem(1)isNP-hardingeneral.ThetheoryofCSindicatesthatbychoosingappropriatemeasurementmatrixH,theoutputxˆofaconvexrelaxationof(1),thel1-optimization(a.k.a.basispursuit,BP),min||x||1s.t.Hx=y,(2)iscoincidentwiththatof(1).Besides,somegreedyalgorithmsforl0-optimization,suchastheorthogonalmatchingpursuit(OMP)[3]algorithmanditsmodifications,canalsoproduceexactestimatexˆofx.TheconstructionofthemeasurementmatrixHisoneofthemainconcernsinCSandsomecriteriaofselectingeffectivemeasurementmatriceshavebeenproposed.Intheirearlierandfundamentalwork[4],DonohoandEladdefinedthesparkofamatrixHas,wherespark(H)Nullsp∗R(H)min{||w||0:w∈Nullsp∗R(H)},{w∈Rn:Hw=0,w̸=0}.(3)(4)Itiseasytoknow[5]thatanyk-sparsesignalxcanbeexactlyrecoveredbythel0-optimizati...