Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Numerical Analysis

254 missions · 180 completed

Missions

Open74Completed180All254
Convex OptimizationOptimization·Captain: iris

A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem: Local Q-Quadratic Convergence of the Modified Semismooth Newton MethodResearch Paper

A doubly stochastic matrix is a nonnegative square matrix whose rows and columns all sum to one. Given an arbitrary matrix X^∈Rn×n\hat X\in\mathbb R^{n\times n}X^∈Rn×n, the nearest doubly stochastic matrix problem asks for the doubly stochastic matrix closest to X^\hat XX^ in the Frobenius norm. It appears as a subproblem in splitting methods (ADMM) for semidefinite…

37 thms6 active usersReviewed
Convex OptimizationOptimization·Captain: iris

Primal-Dual Extrapolation Methods for Monotone Inclusions Under Local Lipschitz Continuity: Algorithm 2 Finds an ϵ\epsilonϵ-Residual Solution in Mˉ=O(ϵ−1log⁡ϵ−1)\bar M=O(\epsilon^{-1}\log\epsilon^{-1})Mˉ=O(ϵ−1logϵ−1) OperationsResearch Paper

Many problems in optimization, saddle-point computation and variational analysis can be written as a monotone inclusion: find x∈Rnx\in\mathbb R^nx∈Rn with 0∈(F+B)(x)0\in(F+B)(x)0∈(F+B)(x). Here BBB is a maximal monotone set-valued operator whose resolvent is cheap, and FFF is a monotone point-valued operator. Forward-backward splitting and its descendants are the standard solvers: they…

20 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 4: Metric Subregularity of ∂L_γ Implies the VP-EB Error BoundResearch Paper

Many problems in signal processing, statistics and engineering design have the form of a nonconvex, possibly nonsmooth objective subject to nonlinear equality constraints. Zhu, Zhao and Zhang (arXiv:2007.12219v1, 2020; published in Mathematics of Operations Research, 2024) propose NAPP-AL, a first-order primal-dual method that takes one linearized step on…

10 thms4 active usersReviewed
Complexity TheoryMachine LearningTheoretical Computer Science·Captain: Shuze Chen

The Cancellation-Free Cost of Hessian Diagonals: Exact Counts, Formulas and InterfacesResearch Paper

Automatic differentiation computes the gradient of a function given as a program at a constant factor over one evaluation [Baur and Strassen 1983; Griewank and Walther 2008]. Second-order quantities are harder. The Hessian diagonal (∂2f/∂xi2)i(\partial^2 f/\partial x_i^2)_i(∂2f/∂xi2​)i​ and its sum, the Laplacian, appear in physics-informed neural networks, variational Monte Carlo…

15 thms3 active usersReviewed
AnalysisQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Time-space tradeoffs for Hamiltonian simulationResearch Paper

A Hamiltonian simulation approximates the evolution of a quantum system from simpler evolutions generated by its constituent terms. Product formulas accomplish this by composing those term evolutions. Their resource cost depends on the desired accuracy, the formula's order, and the number of repetitions. A coherent circuit can also select among several such…

31 thms3 active usersReviewed
Mathematical PhysicsOptimizationProbability+1·Captain: Shuze Chen

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick ModelResearch Paper

The Sherrington–Kirkpatrick (SK) model is the basic mean-field spin glass: for a random symmetric Gaussian matrix AAA, find a spin vector σ∈{−1,1}N\sigma\in\{-1,1\}^Nσ∈{−1,1}N maximizing the energy HN(σ)=12σ⊤AσH_N(\sigma)=\tfrac12\sigma^\top A\sigmaHN​(σ)=21​σ⊤Aσ. Finding the exact maximizer is a hard combinatorial problem in the worst case, and the question of how close polynomial-time algorithms can…

23 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Nearly optimal Personalized PageRank computationResearch Paper

Personalized PageRank assigns importance to vertices relative to a chosen seed. A walk starts at the seed and stops with probability α\alphaα at each step; its stopping location has the PageRank distribution. Small teleportation probabilities let the walk explore farther, but make the running time of the classic local computation grow. This matters when…

42 thms3 active usersReviewed
Linear algebraTheoretical Computer Science·Captain: iris

Solving Linear Systems in O~(mnlog⁡κϵ)\tilde{O}(m n \log \frac{\kappa}{\epsilon})O~(mnlogϵκ​) Bit OperationsResearch Paper

Solving a square linear system Ax=bAx = bAx=b to a prescribed relative residual is a basic task of numerical computation, and its cost in bit operations is the honest measure of that task: it charges for the length of every number the algorithm touches. For a sparse matrix with mmm nonzero entries, conjugate-gradient type methods use O(mn)O(mn)O(mn) arithmetic operations in…

28 thms3 active usersReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: iris

From smoothed analysis to backward error: The power of adaptive perturbationsResearch Paper

A backward-stable solution of a linear system Ax=bAx=bAx=b is a vector x~\tilde xx~ that solves a nearby system exactly: (A+Δ)x~=b(A+\Delta)\tilde x=b(A+Δ)x~=b with ∥Δ∥2≤ε∥A∥2\|\Delta\|_2\le\varepsilon\|A\|_2∥Δ∥2​≤ε∥A∥2​. Backward error is the standard accuracy notion of numerical linear algebra, and it makes sense even when AAA is singular or badly conditioned. A natural way to obtain it is borrowed from smoot…

32 thms3 active usersReviewed
Convex OptimizationOptimizationTheoretical Computer Science·Captain: iris

Solving ppp-norm regression in matrix multiplication timeResearch Paper

Given a matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d of full column rank and a vector b∈Rnb\in\mathbb R^nb∈Rn, ℓp\ell_pℓp​ regression asks for a minimizer of ∥Ax−b∥p\|Ax-b\|_p∥Ax−b∥p​. The case p=2p=2p=2 is least squares; p∈{1,∞}p\in\{1,\infty\}p∈{1,∞} is equivalent to linear programming; the values in between interpolate between linear system solving and linear programming and arise in data analysis and in flow…

34 thms3 active usersReviewed
Linear algebraOptimization·Captain: iris

Global Sinkhorn Convergence and Spectral Stability of Matrix ScalingResearch Paper

Matrix scaling asks for positive diagonal matrices X,YX,YX,Y that turn a nonnegative square matrix AAA into a matrix XAYXAYXAY with prescribed row and column sums; here the target is a doubly stochastic matrix. Classical uses include adjusting contingency tables to given marginal totals (Deming and Stephan, 1940), and a prominent modern one is entropically regularized…

31 thms3 active usersReviewed
Convex OptimizationOptimization·Captain: iris

Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS RelaxationsResearch Paper

Minimizing a polynomial fff over the Boolean cube {±1}n\{\pm1\}^n{±1}n contains MAX-CUT, Ising ground states and many other combinatorial problems. The moment–sum-of-squares (moment–SOS) hierarchy replaces the cube by a semidefinite program (SDP) of order ddd; when the relaxation is exact, its optimum is the rank-one moment matrix of the Boolean minimizer, and an optimal …

31 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

An Equivalent Reformulation and Multi-Proximity Gradient Algorithms for a Class of Nonsmooth Fractional Programming: Under the KL Property, the Iterates of CMPGA_ML Converge to a Critical PointResearch Paper

Many models in signal processing and statistics minimize a ratio of two functions. A prominent family is scale-invariant sparse recovery: the L1/L2L_1/L_2L1​/L2​ model minimizes ∥x∥1/∥x∥2+λ2∥Ax−b∥22\|x\|_1/\|x\|_2+\tfrac\lambda2\|Ax-b\|_2^2∥x∥1​/∥x∥2​+2λ​∥Ax−b∥22​ over a box, and the L1/SKL_1/S_KL1​/SK​ model divides ∥x∥1+λ2∥Ax−b∥22\|x\|_1+\tfrac\lambda2\|Ax-b\|_2^2∥x∥1​+2λ​∥Ax−b∥22​ by the sum of the KKK largest entries of ∣x∣|x|∣x∣ (Rahimi–Wang–Dong–Lou, SIAM J.…

30 thms3 active usersReviewed
Convex OptimizationOptimization·Captain: iris

A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization: Global Linear Convergence of the Exact Homotopy Scheme under Strong Convexity and Lipschitz GradientResearch Paper

Composite convex problems min⁡xf(x)+g(x)\min_x f(x)+g(x)minx​f(x)+g(x), with fff smooth and ggg nonsmooth, cover the regularized estimation and constrained models of statistics, signal processing and machine learning. Proximal variable-metric methods (Lee, Sun and Saunders, 2014) solve them with a metric that adapts to the curvature of fff, but each step is a scaled proximal subproblem,…

29 thms3 active usersReviewed
Convex OptimizationOptimization·Captain: iris

A Squared Smoothing Newton Method for Semidefinite Programming: Under Primal and Dual Constraint Nondegeneracy the Huber-Based Method Converges Superlinearly with Order 1+τ1+\tau1+τResearch Paper

Semidefinite programming (SDP) minimizes a linear function of a symmetric matrix subject to linear equations and positive semidefiniteness. It is a standard modelling tool in control, combinatorial optimization, statistics and quantum information. Interior point methods solve SDPs accurately but each iteration factorizes a dense m×mm\times mm×m Schur complement,…

22 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems: One PolyakBundle Step Gives f(x̃) − f* ≤ Cₛ(f(x) − f*)^(1+η) Near a Sharp (b)-Regular MinimizerResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R from first-order information alone. At a sharp minimum, where fff grows at least linearly away from its solution set, the Polyak step x+=x−f(x)−f∗∥v∥2vx^+=x-\frac{f(x)-f^*}{\|v\|^2}vx+=x−∥v∥2f(x)−f∗​v converges linearly (Polyak 1969; in the convex and weakly convex settings, Davis,…

15 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

A 0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming: SNSCO Takes Full Newton Steps and Converges Locally Superlinearly or QuadraticallyResearch Paper

A chance constrained program minimizes a cost while requiring a random constraint to hold with high probability. It models decisions under uncertainty in energy systems, finance, and process and water-quality engineering. Replacing the probability by an empirical frequency over NNN samples gives the sample average approximation, whose constraint counts the…

16 thms3 active usersReviewed
Complexity TheoryOptimizationQuantum Information·Captain: mikedeng1

Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation: an ε-Accurate Gradient of a Smooth Analytic Function from Õ(c√d/ε · log(d/δ)) Phase-Oracle QueriesResearch Paper

Many proposed quantum optimization and machine-learning methods (variational quantum eigensolvers, QAOA, quantum classifiers) tune the real parameters of a circuit by gradient descent on an objective f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R that is only accessible as a black box. Classically, a finite-difference estimate of ∇f\nabla f∇f costs on the order of ddd evaluations of fff…

14 thms3 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 2: Under the VP-EB Error Bound, NAPP-AL Converges Linearly to a Stationary PointResearch Paper

Many problems in machine learning, signal processing and engineering design minimize a nonconvex, possibly nonsmooth objective subject to nonlinear equality constraints. Augmented Lagrangian methods are the standard tool for such constraints, but each classical iteration solves a hard nonconvex subproblem. Zhu, Zhao and Zhang (arXiv:2007.12219v1, published…

9 thms3 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 2: Finite, Linear or Sublinear Rates for the Iterates Under the Łojasiewicz PropertyResearch Paper

The alternating direction method of multipliers (ADMM) is one of the standard splitting methods for problems of the form min⁡x{g(Ax)+h(x)}\min_x\{g(Ax) + h(x)\}minx​{g(Ax)+h(x)}, in which a nonsmooth term acts on a linear image of the variable. It is used in signal and image processing, statistical learning and matrix completion, and in many of these applications ggg or hhh is nonconvex:…

14 thms3 active usersReviewed
Linear algebraOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method IV: Global Convergence for Small Perturbations of M-MatricesResearch Paper

Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψy \le \psiy≤ψ and λ≥0\lambda \ge 0λ≥0 with Ay+λ=fAy + \lambda = fAy+λ=f and λi(yi−ψi)=0\lambda_i(y_i - \psi_i) = 0λi​(yi​−ψi​)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…

10 thms3 active usersReviewed
Optimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method I: Local Superlinear Convergence for P-Matrix Complementarity ProblemsResearch Paper

Many problems in optimization and in the discretization of partial differential equations reduce to a linear complementarity problem with an obstacle: find y,λ∈Rny, \lambda \in \mathbb{R}^ny,λ∈Rn with

8 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Golden Ratio Algorithms for Variational Inequalities II: The Explicit Golden Ratio Algorithm Converges for Locally Lipschitz Monotone OperatorsResearch Paper

Monotone variational inequalities cover convex minimisation, convex–concave saddle-point problems, Nash equilibria of monotone games and complementarity problems, and they are the standard model for these in optimization and operations research. First-order methods for them (extragradient, forward–backward–forward, reflected and projected gradient methods)…

18 thms3 active users
Convex OptimizationLinear algebra·Captain: mikedeng1

A Fast and Accurate Algorithm for the p→qp \to qp→q Norm of Sparse Non-Negative MatricesResearch Paper

The p→qp \to qp→q norm of a matrix generalizes the largest singular value (p=q=2p = q = 2p=q=2) to ℓp\ell_pℓp​ geometries. For general matrices it is efficiently computable only when p=1p = 1p=1, q=∞q = \inftyq=∞, or p=q∈{1,2,∞}p = q \in \{1, 2, \infty\}p=q∈{1,2,∞}, and in the non-hypercontractive regime p≥q≥1p \ge q \ge 1p≥q≥1 it is NP-hard to approximate within any constant factor for 1<q≤p<21 < q \le p < 21<q≤p<2 or …

22 thms2 active usersReviewed
Probability·Captain: mikedeng1

Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random MatricesResearch Paper

Gaussian elimination with partial pivoting (GEPP) solves a dense real linear system by exchanging rows and subtracting multiples of a pivot row. Its numerical accuracy depends partly on whether these operations create entries much larger than the input entries. This matters to numerical analysts studying when a fast general-purpose solver can lose accuracy,…

33 thms2 active usersReviewed
PreviousPage 1 of 3Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me