CUHK electronic theses & dissertations collection

Rank minimization with affine constraints has various applications in different area. Due to the intractability of rank function in the objective, many alternative functions have been widely studied in the literature, e.g., nuclear norm, and have been shown an effective way both theoretically and practically. The intractability was bypassed as those functions hold some nice properties such as convexity and differentiability. In this dissertation, we make efforts to improve the rank minimization performance while retaining computation efficiency by exploring the use of a non-convex surrogate of the rank function, namely the so-called Schatten quasi p norm (0 < p < 1). Although the resulting optimization problem is non-convex, we show, for the first time, that a first-order critical point can be approximated to arbitrary accuracy in polynomial time using the proposed potential reduction algorithm in this dissertation.We then apply the resulting potential reduction algorithm to Sensor Network Localization problem. Currently, a popular approach to localization is using convex relaxation. In a typical application of this approach, the localization problem is first formulated as a rank-constrained semidefinite program (SDP), where the rank corresponds to the target dimension in which the sensors should be localized. Then, the non-convex rank constraint is either dropped or replaced by a convex approximation, thus resulting into a convex optimization problem. Our potential reduction algorithm is applied to the localization problem while the Schatten quasi p norm is employed in localization aiming to minimize the solution rank. Moreover, we show that the first-order critical point, the output of the algorithm, is already suffcient for recovering the node locations in the target dimension if the input instance satisfies certain conditions which has been shown in the literature. Finally, our simulation results show that in many scenarios, our proposed algorithm can achieve better localization in terms of accuracy than the popular SDP relaxations of the problem and its variations.线性约束下的矩阵秩最小化在诸多领域有着广泛的应用。然而由于秩的复杂性质，许多研究致力于寻找它的替代函数。例如，核模是其中非常流行的一种，研究已经表明其在理论和应用上的有效性。由于这些替代函数往往具有秩函数所没有的特性，比如凸性，可微分性等等，正是由于这些特性使得其在计算上有着更高的效率保证。在本文中，我们希望通过一种非凸的替代函数来提高这种替代方法的有效性，并且在同时希望能继续保持在计算上的效率，我们使用的这种非凸替代函数被称为Schatten 拟p 模（0 < p < 1）。尽管该优化问题的目标函数是非凸的，我们还是能够第一次证明可以在多项式时间内以任意精度逼近该问题的一阶临界点。同时，我们将得到的势削减算法应用于传感器网络定位问题中。当前，处理该问题的流行方法是使用凸放松。在这种方法中，我们首先将传感器网络定位问题写成一个秩限制条件下的半正定规划问题，它的秩限制条件对应于传感器所在空间的维度。在凸放松方法中，通常这些秩限制条件被直接去除，或者被一个凸函数取代。在我们的方法中，我们使用Schatten拟模作为惩罚函数来优化所得解的秩。我们还证明了在某些条件被满足的情况下，该问题的一阶临界点已经足够用来还原节点的位置。最后我们对多种情景做了模拟实验，结果表明我们提出的算法在准确性上相比流行的半正定规划及其衍生的方法更有优势。Ji, Senshan.Thesis Ph.D. Chinese University of Hong Kong 2015.Includes bibliographical references (leaves 102-110).Abstracts also in Chinese.Title from PDF title page (viewed on 06, October, 2016).Detailed summary in vernacular field only.Detailed summary in vernacular field only