This paper introduces a new storage-optimal first-order method (FOM), CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently. We accompany our theoretical results with preliminary numerical experiments suggesting that CertSDP significantly outperforms current state-of-the-art methods on large sparse exact QMP-like SDPs.
相關內容
Leveraging on recent advancements on adaptive methods for convex minimization problems, this paper provides a linesearch-free proximal gradient framework for globalizing the convergence of popular stepsize choices such as Barzilai-Borwein and one-dimensional Anderson acceleration. This framework can cope with problems in which the gradient of the differentiable function is merely locally H\"older continuous. Our analysis not only encompasses but also refines existing results upon which it builds. The theory is corroborated by numerical evidence that showcases the synergetic interplay between fast stepsize selections and adaptive methods.
The iterated Arnoldi-Tikhonov (iAT) method is a regularization technique particularly suited for solving large-scale ill-posed linear inverse problems. Indeed, it reduces the computational complexity through the projection of the discretized problem into a lower-dimensional Krylov subspace, where the problem is then solved. This paper studies iAT under an additional hypothesis on the discretized operator. It presents a theoretical analysis of the approximation errors, leading to an a posteriori rule for choosing the regularization parameter. Our proposed rule results in more accurate computed approximate solutions compared to the a posteriori rule recently proposed in arXiv:2311.11823. The numerical results confirm the theoretical analysis, providing accurate computed solutions even when the new assumption is not satisfied.
We show that established performance metrics in binary classification, such as the F-score, the Jaccard similarity coefficient or Matthews' correlation coefficient (MCC), are not robust to class imbalance in the sense that if the proportion of the minority class tends to $0$, the true positive rate (TPR) of the Bayes classifier under these metrics tends to $0$ as well. Thus, in imbalanced classification problems, these metrics favour classifiers which ignore the minority class. To alleviate this issue we introduce robust modifications of the F-score and the MCC for which, even in strongly imbalanced settings, the TPR is bounded away from $0$. We numerically illustrate the behaviour of the various performance metrics in simulations as well as on a credit default data set. We also discuss connections to the ROC and precision-recall curves and give recommendations on how to combine their usage with performance metrics.
This contribution draws attention to implications connected with meta-architectural design decisions for intelligent tutoring systems in the context of formative assessments. As a first result of addressing this issue, this contribution presents a meta-architectural system design that includes the role of educators.
Sparse recovery principles play an important role in solving many nonlinear ill-posed inverse problems. We investigate a variational framework with support Oracle for compressed sensing sparse reconstructions, where the available measurements are nonlinear and possibly corrupted by noise. A graph neural network, named Oracle-Net, is proposed to predict the support from the nonlinear measurements and is integrated into a regularized recovery model to enforce sparsity. The derived nonsmooth optimization problem is then efficiently solved through a constrained proximal gradient method. Error bounds on the approximate solution of the proposed Oracle-based optimization are provided in the context of the ill-posed Electrical Impedance Tomography problem. Numerical solutions of the EIT nonlinear inverse reconstruction problem confirm the potential of the proposed method which improves the reconstruction quality from undersampled measurements, under sparsity assumptions.
In this paper, we propose a new algorithm, the irrational-window-filter projection method (IWFPM), for solving arbitrary dimensional global quasiperiodic systems. Based on the projection method, IWFPM further utilizes the concentrated distribution of Fourier coefficients to filter out relevant spectral points using an irrational window. Moreover, a corresponding index-shift transform is designed to make the Fast Fourier Transform available. The corresponding error analysis on the function approximation level is also given. We apply IWFPM to 1D, 2D, and 3D quasiperiodic Schr\"odinger eigenproblems to demonstrate its accuracy and efficiency. For both extended and localized quantum states, IWFPM exhibits a significant computational advantage over PM. Furthermore, the widespread existence of such spectral point distribution feature can endow IWFPM with significant potential for broader applications in quasiperiodic systems.
This paper derives a discrete dual problem for a prototypical hybrid high-order method for convex minimization problems. The discrete primal and dual problem satisfy a weak convex duality that leads to a priori error estimates with convergence rates under additional smoothness assumptions. This duality holds for general polyhedral meshes and arbitrary polynomial degrees of the discretization. A novel postprocessing is proposed and allows for a~posteriori error estimates on regular triangulations into simplices using primal-dual techniques. This motivates an adaptive mesh-refining algorithm, which performs superiorly compared to uniform mesh refinements.
This paper shows how to use the shooting method, a classical numerical algorithm for solving boundary value problems, to compute the Riemannian distance on the Stiefel manifold $ \mathrm{St}(n,p) $, the set of $ n \times p $ matrices with orthonormal columns. The proposed method is a shooting method in the sense of the classical shooting methods for solving boundary value problems; see, e.g., Stoer and Bulirsch, 1991. The main feature is that we provide an approximate formula for the Fr\'{e}chet derivative of the geodesic involved in our shooting method. Numerical experiments demonstrate the algorithms' accuracy and performance. Comparisons with existing state-of-the-art algorithms for solving the same problem show that our method is competitive and even beats several algorithms in many cases.
This paper presents and evaluates a set of methods to classify individual Scopus publications using their references back to the second generation, where each publication can be assigned fractionally into up to five ASJC (All Science Journal Classifications) categories, excluding the Multidisciplinary area and the miscellaneous categories. Based on proposals by Glanzel et al. (1999a, 1999b, 2021), some additional parameters are established that allow different results to be obtained depending on how category membership is weighted or how the acceptance thresholds for multiple assignments are established. Various classifications are obtained, and then compared with each other, with the original ASJC Scopus journal classification, and with the AAC (Authors Assignation Collection) classification of a previous study (Alvarez-Llorente et al., 2023) in which the papers corresponding authors assign them the most appropriate categories. Classifications in which a high threshold is set for allowing assignments to multiple categories, combined with the use of first- and second-generation references and averaging over the number of references, provide the most promising results, improving over other reference-based reclassification proposals in terms of granularity, and over the Scopus classification itself in such aspects as the homogeneity of the publications assigned to a category. They also show greater coincidence with the AAC classification.
This paper explores the extension of dimension reduction (DR) techniques to the multi-dimension case by using the Einstein product. Our focus lies on graph-based methods, encompassing both linear and nonlinear approaches, within both supervised and unsupervised learning paradigms. Additionally, we investigate variants such as repulsion graphs and kernel methods for linear approaches. Furthermore, we present two generalizations for each method, based on single or multiple weights. We demonstrate the straightforward nature of these generalizations and provide theoretical insights. Numerical experiments are conducted, and results are compared with original methods, highlighting the efficiency of our proposed methods, particularly in handling high-dimensional data such as color images.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191