随着因特网的日益普及,移动通信的迅猛发展,以及各种多媒体业务(如高清电视、视频监控、视频检索、数字图书馆等)的涌现,在模式识别、计算机视觉、机器学习和数据挖掘等领域,人们经常需要学习、研究与存储维度更高、结构更复杂、规模更大的数据。高维信号自身含有较高的稀疏性、相关性和冗余性,如何在各种情况下,合理、高效地利用信号结构上的特性,进而将原始信号从被噪声污染或者部分受损的高维及高阶复杂信号中完整重构出来,已经成为信号和图像处理领域的一个重要的研究方向,也是本文的主要研究内容。基于压缩感知的矩阵秩极小化、低秩矩阵恢复理论是一种重要的高维数据分析方法。本论文对现有压缩感知、矩阵秩极小化和低秩矩阵恢复理论进行了系统的总结和分析,并深入研究结构稀疏相关的矩阵重建算法。现有凸优化算法利用l1范数约束信号的稀疏性。l1范数假设每个元素是独立受损的,而在一些实际问题中,稀疏信号的非零元素往往不仅是独立的,而且彼此之间还表现出一定的相关特性。此外,现有算法中核范数并不能完全正确地逼近矩阵的秩函数。针对低秩矩阵恢复算法的不足之处,本文首先提出基于低秩和结构稀疏(l1,2范数)的矩阵分解算法,然后,结合监控视频的背景先验知识,设计了一种更好的秩估计策略,并提出了一种改进的交替方向算法,直接实现监控视频序列中背景和前景的分离。最后,在增广拉格朗日乘子法框架下,本文研究了一种收敛更快的非精确增广拉格朗日乘子法。该算法采用块Lanczos方法和热启动技术实现部分奇异值分解,使得原有算法的计算量和迭代次数得以控制。基于实际监控视频的实验结果表明,本文提出的算法恢复出的背景矩阵更为低秩,能够更加简洁高效地解决背景建模这一实际问题。