Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFeasibility and A Fast Algorithm for Euclidean Distance Matrix Optimization with Ordinal Constraints
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Euclidean distance matrix optimization with ordinal constraints (EDMOC) has found important applications in sensor network localization and molecular conformation. It can also be viewed as a matrix formulation of multidimensional scaling, which is to embed n points in a $r$-dimensional space such that the resulting distances follow the ordinal constraints. The ordinal constraints, though proved to be quite useful, may result in only zero solution when too many are added, leaving the feasibility of EDMOC as a question. In this paper, we first study the feasibility of EDMOC systematically. We show that if $rge n-2$, EDMOC always admits a nontrivial solution. Otherwise, it may have only zero solution. The latter interprets the numerical observations of crowding phenomenon. Next we overcome two obstacles in designing fast algorithms for EDMOC, i.e., the low-rankness and the potential huge number of ordinal constraints. We apply the technique developed to take the low rank constraint as the conditional positive semidefinite cone with rank cut. This leads to a majorization penalty approach. The ordinal constraints are left to the subproblem, which is exactly the weighted isotonic regression, and can be solved by the enhanced implementation of Pool Adjacent Violators Algorithm (PAVA). Extensive numerical results demonstrate {the} superior performance of the proposed approach over some state-of-the-art solvers.
rate research
Read More
This paper addresses the problem of low-rank distance matrix completion. This problem amounts to recover the missing entries of a distance matrix when the dimension of the data embedding space is possibly unknown but small compared to the number of considered data points. The focus is on high-dimensional problems. We recast the considered problem into an optimization problem over the set of low-rank positive semidefinite matrices and propose two efficient algorithms for low-rank distance matrix completion. In addition, we propose a strategy to determine the dimension of the embedding space. The resulting algorithms scale to high-dimensional problems and monotonically converge to a global solution of the problem. Finally, numerical experiments illustrate the good performance of the proposed algorithms on benchmarks.
We study smooth stochastic optimization problems on Riemannian manifolds. Via adapting the recently proposed SPIDER algorithm citep{fang2018spider} (a variance reduced stochastic method) to Riemannian manifold, we can achieve faster rate than known algorithms in both the finite sum and stochastic settings. Unlike previous works, by emph{not} resorting to bounding iterate distances, our analysis yields curvature independent convergence rates for both the nonconvex and strongly convex cases.
Clustering has been one of the most basic and essential problems in unsupervised learning due to various applications in many critical fields. The recently proposed sum-of-nums (SON) model by Pelckmans et al. (2005), Lindsten et al. (2011) and Hocking et al. (2011) has received a lot of attention. The advantage of the SON model is the theoretical guarantee in terms of perfect recovery, established by Sun et al. (2018). It also provides great opportunities for designing efficient algorithms for solving the SON model. The semismooth Newton based augmented Lagrangian method by Sun et al. (2018) has demonstrated its superior performance over the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). In this paper, we propose a Euclidean distance matrix model based on the SON model. An efficient majorization penalty algorithm is proposed to solve the resulting model. Extensive numerical experiments are conducted to demonstrate the efficiency of the proposed model and the majorization penalty algorithm.
Gradient-free optimization methods, such as surrogate based optimization (SBO) methods, and genetic (GAs), or evolutionary (EAs) algorithms have gained popularity in the field of constrained optimization of expensive black-box functions. However, constraint-handling methods, by both classes of solvers, do not usually guarantee strictly feasible candidates during optimization. This can become an issue in applied engineering problems where design variables must remain feasible for simulations to not fail. We propose a constraint-handling method for computationally inexpensive constraint functions which guarantees strictly feasible candidates when using a surrogate-based optimizer. We compare our method to other SBO, GA/EA and gradient-based algorithms on two (relatively simple and relatively hard) analytical test functions, and an applied fully-resolved Computational Fluid Dynamics (CFD) problem concerned with optimization of an undulatory swimming of a fish-like body, and show that the proposed algorithm shows favorable results while guaranteeing feasible candidates.
In this article, we study algorithms for nonnegative matrix factorization (NMF) in various applications involving streaming data. Utilizing the continual nature of the data, we develop a fast two-stage algorithm for highly efficient and accurate NMF. In the first stage, an alternating non-negative least squares (ANLS) framework is used, in combination with active set method with warm-start strategy for the solution of subproblems. In the second stage, an interior point method is adopted to accelerate the local convergence. The convergence of the proposed algorithm is proved. The new algorithm is compared with some existing algorithms in benchmark tests using both real-world data and synthetic data. The results demonstrate the advantage of our algorithm in finding high-precision solutions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
