No abstract uploaded!

No abstract uploaded!

Kurdyka–Łojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of 1/2 for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is 1/2 for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve C2-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group-fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices of rank at most k.

We consider the edge statistics of large dimensional deformed rectangular matrices of the form $Y_t=Y+\sqrt{t}X,$ where $Y$ is a $p \times n$ deterministic signal matrix whose rank is comparable to $n$, $X$ is a $p\times n$ random noise matrix with centered i.i.d. entries with variance $n^{-1}$, and $t>0$ gives the noise level. This model is referred to as the interference-plus-noise matrix in the study of massive multiple-input multiple-output (MIMO) system, which belongs to the category of the so-called signal-plus-noise model. For the case $t=1$, the spectral statistics of this model have been studied to a certain extent in the literature \cite{DOZIER20071099,DOZIER2007678,VLM2012}. In this paper, we study the singular value and singular vector statistics of $Y_t$ around the right-most edge of the singular value spectrum in the harder regime $n^{-2/3}\ll t \ll 1$. This regime is harder than the $t=1$ case, because on one hand, the edge behavior of the empirical spectral distribution (ESD) of $YY^\top$ has a strong effect on the edge statistics of $Y_tY_t^\top$ since $t\ll 1$ is ``small", while on the other hand, the edge statistics of $Y_t$ is also not merely a perturbation of those of $Y$ since $t\gg n^{-2/3}$ is ``large". Under certain regularity assumptions on $Y,$ we prove the edge universality, eigenvalues rigidity and eigenvector delocalization for the matrices $Y_tY_t^\top$ and $Y_t^\top Y_t$. These results can be used to estimate and infer the massive MIMO system. To prove the main results, we analyze the edge behavior of the asymptotic ESD for $Y_tY_t^\top$, and establish some sharp local laws on the resolvent of $Y_tY_t^\top$. These results can be of independent interest, and used as useful inputs for many other problems regarding the spectral statistics of $Y_t$.

We consider the problem of minimizing the sum of a smooth function h with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function P and a surjective linear map M. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions h and P are semialgebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the 1/2 regularization. Finally, when M is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex h. We illustrate our theoretical finding with a variety of applications such as signal denoising and sparse optimisation problems.