实际工程中待处理的信号往往具有结构化的特征,其中稀疏性和低秩性是两种简单且普遍存在的结构,如何利用信号结构提升性能是近年来信号处理领域的学术前沿。在求解稀疏重建问题的算法中,非凸优化类算法性能最好,但是这类算法缺乏从初始点收敛到最稀疏信号的理论保证。另外,实际应用中存在各种噪声和误差,重建算法在有噪声情形下的抗噪声性能非常重要,但是目前缺乏贪婪类算法在全噪声情形下与Oracle重建的性能比较。针对这两个关键问题,本文开展了一系列的研究工作。首先,本文理论研究了l_p“范数”(0≤p<1)最小化问题的全局和局部最优性。提出了一类能够近似l_p“范数”的非凸函数,定义这类函数的非凸程度度量。理论证明了对应非凸优化问题的全局最优性趋于l_p“范数”最小化问题的全局最优性,得到为保证最稀疏信号在其邻域内是非凸优化问题唯一的局部极小值,非凸程度与邻域半径应该满足的关系,为理论分析求解算法的收敛性打下了基础。其次,本文面向不同场景设计了不同的非凸优化问题求解算法,证明了为保证算法收敛到最稀疏信号,非凸程度应该与算法初始点到最稀疏信号之间距离成反比的结论,得到了算法所需的迭代次数和重建误差的上界,解决了第一个关键问题。通过数值仿真验证了理论结果,表明非凸优化类算法能重建非零元素更多的信号,运行时间更短,抗噪声性能更好。再次,本文将针对稀疏重建问题开展的研究工作推广至低秩重建问题,定义了一类能够诱导矩阵低秩性且具有非凸程度度量的函数,提出了非凸优化问题的求解算法,研究得到了保证算法从初始点收敛到最低秩矩阵的充分条件。数值仿真验证了理论结果,并表明提出的算法是性能最好的算法之一。最后,本文基于回溯思想提出了回溯匹配追踪算法,研究了当观测值、感知矩阵和最稀疏信号上均存在加性噪声时,该算法的重建误差与各类噪声强度的关系。通过与Oracle重建的误差下界进行对比,表明该算法具有与Oracle重建同阶的抗噪声性能,解决了第二个关键问题。本文的研究工作为性能优异的非凸优化类算法提供了收敛性保证,为贪婪类算法提供了抗噪声性能分析,推进了算法的实用化进程,同时也促进了非凸优化理论的发展。