| 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 sufficient 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. |
