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
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data I: The Worst-Case Residual and Its Unique MinimizerResearch Paper

The least-squares (LS) problem min⁡x∥Ax−b∥\min_x \|Ax - b\|minx​∥Ax−b∥ assumes that the data A∈Rn×mA \in \mathbb{R}^{n\times m}A∈Rn×m, b∈Rnb \in \mathbb{R}^nb∈Rn are exact. In applications they rarely are: they come from measurements, from linearizations, or from models with neglected dynamics. A classical response is sensitivity analysis or regularization (Tikhonov), where a weight trades the size…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Projected Gradient Methods for Linearly Constrained Problems I: The Gradient Projection Method Drives the Projected Gradients to ZeroResearch Paper

The gradient projection method minimizes a continuously differentiable function over a closed convex set by alternating a gradient step with a projection back onto the set. It was proposed by Goldstein (1964) and by Levitin and Polyak (1966), and it is the basic step of many algorithms for bound constrained and linearly constrained optimization, including…

16 thms3 active usersReviewed
🏆Completed
Linear algebraProbabilityRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix I: Sample Bound for the Gaussian Trace EstimatorResearch Paper

Many computations in scientific computing, statistics and machine learning need the trace of a matrix AAA that is never formed explicitly: AAA may be f(B)f(B)f(B) for a large sparse BBB, an inverse B−1B^{-1}B−1, or a product of operators, and the only access to it is the ability to compute products AzAzAz for chosen vectors zzz. Examples are log-determinant estimation in Gaussian…

9 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

Analysis of Generalized Pattern Searches: Nonnegative Clarke Derivatives at Limits of Refining SubsequencesResearch Paper

Generalized pattern search (GPS) is a class of derivative-free methods for minimizing a function that can only be evaluated, not differentiated. Such objectives arise in engineering design, where one evaluation is an expensive simulation that may fail and return no value at all. The helicopter rotor design problem of Booker et al. is one example: no value…

13 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Nonsmooth Version of Newton's Method I: local superlinear convergence of the generalized-Jacobian Newton method at a semismooth regular rootResearch Paper

Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0F(x) = 0F(x)=0 whose map F:Rn→RnF : \mathbb R^n \to \mathbb R^nF:Rn→Rn is Lipschitz but not differentiable: reformulations of nonlinear complementarity problems through the componentwise minimum or the Fischer–Burmeister function, Karush–Kuhn–Tucker systems of constrained programs, and…

14 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Updating Quasi-Newton Matrices with Limited Storage: The Limited-Storage BFGS Method Reaches the Minimizer of a Strictly Convex Quadratic in at Most n StepsResearch Paper

Quasi-Newton methods minimize a smooth function fff on Rn\mathbb{R}^nRn by moving along dk=−Hkgkd_k = -H_k g_kdk​=−Hk​gk​, where gkg_kgk​ is the gradient and HkH_kHk​ is an approximation of the inverse Hessian built from observed gradient differences. The BFGS update is the most widely used way of building HkH_kHk​, but it stores a dense n×nn \times nn×n matrix, which is prohibitive for large nnn.

16 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Methods of Conjugate Gradients for Solving Linear Systems II: Each Conjugate Gradient Step Shortens the Error VectorResearch Paper

The conjugate gradient method (cg-method) of Hestenes and Stiefel is the standard iterative solver for linear systems Ax=kAx=kAx=k with a symmetric positive definite matrix AAA. It is used for the large sparse systems of finite-element and finite-difference discretizations, as the inner solver of Newton-type and interior-point methods in optimization, and as the…

9 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Methods of Conjugate Gradients for Solving Linear Systems I: Finite Termination of the Conjugate Gradient MethodResearch Paper

Solving a linear system Ax=kAx = kAx=k with a large symmetric positive definite matrix AAA is a basic task of scientific computing: it arises from discretized elliptic equations, least-squares problems and the Newton steps of optimization methods. In 1952 Magnus Hestenes and Eduard Stiefel published the conjugate gradient method (cg-method) (J. Res. Natl. Bur. Stand.…

11 thms3 active usersReviewed
🏆Completed
Algebra·Captain: LG

Métodos Numéricos (Freitas) III: Sistemas Lineares e a Convergência de Gauss-SeidelTextbook

Linear systems are the inner loop of scientific computing: discretized differential equations, least-squares fitting, network flow balances and equilibrium models all end in Ax=bAx = bAx=b. Direct elimination solves the system exactly in O(n3)O(n^3)O(n3) operations, but for the large sparse systems produced by discretization the cost and the round-off growth make iterative…

8 thms3 active usersReviewed
🏆Completed
Analysis·Captain: LG

Métodos Numéricos (Freitas) I: Zeros de Funções e Convergência do Método de NewtonTextbook

Most equations that arise in applications cannot be solved in closed form: the age of the Moon from a radioactive-decay balance, the deflection of a clamped beam, the equilibrium of a catenary, all reduce to solving f(x)=0f(x) = 0f(x)=0 for a function fff with no algebraic inverse. A first course in numerical methods therefore opens with root finding: constructive…

9 thms3 active usersReviewed
🏆Completed
Analysis·Captain: LG

Métodos Numéricos (Freitas) V: Interpolação Polinomial e o Erro da Fórmula de LagrangeTextbook

A table of values is all one has of many functions: measurements, tabulated physical constants, the output of an expensive simulation. Interpolation reconstructs a function between tabulated points by passing a polynomial through them, and it underlies much of the rest of numerical analysis — quadrature rules, finite-difference formulas and…

7 thms3 active usersReviewed
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
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

High Precision Multiplicative-Error Approximation of #SAC¹ Functions in Logspace Uniform AC¹Research Paper

Counting computations can produce integers whose binary expansions are much longer than their inputs. A short arithmetic circuit may repeatedly multiply values, making exact output expensive even when the circuit itself has a compact description. An approximation can have a short floating-point representation, but a small absolute error does not by itself…

26 thms2 active usersReviewed
Linear algebraRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Dimension-Free ℓ22\ell_2^2ℓ22​-Sampling Algorithms for Eigenvalue EstimationResearch Paper

Computing the eigenvalues of a symmetric matrix is a basic primitive of numerical linear algebra, data analysis and spectral algorithms. Classical methods read every entry, which costs Ω(n2)\Omega(n^2)Ω(n2) for a dense n×nn\times nn×n matrix. Bhattacharjee, Dexter, Drineas, Musco and Ray ([BDD+24], Algorithmica 2024) asked whether a sublinear number of entry queries…

33 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Delegating Computation with Approximate Arithmetic: Interactive Proofs for WizardsResearch Paper

Interactive proofs let a computationally weak verifier check a computation carried out by an untrusted prover (Goldwasser–Micali–Rackoff 1989, Babai 1985). The protocol of Goldwasser, Kalai and Rothblum (GKR, JACM 2015) makes this efficient for both parties for arithmetic circuits over a finite field: the prover runs in time polynomial in the circuit size,…

26 thms2 active usersReviewed
Differential GeometryOptimization·Captain: iris

A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Submanifolds: RSSD Accumulation Points Are Stationary, and Limiting Stationary under Gradient Sub-ConsistencyResearch Paper

Many estimation problems in signal processing and statistics ask for a sparse or robust solution under an orthogonality or normalization constraint: finding the sparsest vector in a linear subspace over the unit sphere, or learning an orthogonal dictionary over the orthogonal group. Sparsity is promoted by penalties such as ∥x∥pp\|x\|_p^p∥x∥pp​ with 0<p<10<p<10<p<1, which are no…

15 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints: Trust-IPM Reaches an Approximate Second-Order SIP in O(1 + (ψµ(x⁰) − ψ*µ)/µ · (L₁/(µτₗ²))^{3/4}) IterationsResearch Paper

Interior point methods (IPMs) are the basis of widely used nonlinear optimization solvers, and in practice they are applied to problems whose constraints are nonconvex. For linear and conic programs the theory is complete: self-concordance gives an O(clog⁡(1/ϵ))O(\sqrt{c}\log(1/\epsilon))O(c​log(1/ϵ)) iteration bound. For nonconvex constraints, the analyses of practical IPMs show…

16 thms2 active usersReviewed
Machine LearningOptimization·Captain: iris

Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence: RISRO Converges Quadratic-Linearly to a Rank-rrr Stationary Point under 2r2r2r-RIPResearch Paper

Many estimation problems ask for a low-rank matrix that fits linear measurements: matrix sensing, matrix completion, phase retrieval, blind deconvolution, and system identification among them. The common core is rank constrained least squares, a non-convex problem that also underlies low-rank recovery theory (Recht, Fazel and Parrilo, 2010). The problem is…

30 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold: ManIAL Reaches an ε-KKT Point Within Õ(ε⁻³) / O(ε⁻³) Oracle CallsResearch Paper

Many estimation problems are posed over a manifold and carry a nonsmooth regularizer: sparse principal component analysis over the Stiefel manifold, nonnegative PCA, low-rank semidefinite programs in factored form. They share the composite form

27 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Ghost Penalties in Nonconvex Constrained Optimization: Diminishing-Stepsize SQP-Type Iterates Have a Generalized Stationary Limit Point, All KKT under eMFCQResearch Paper

Diminishing stepsizes, γν→0\gamma^\nu\to 0γν→0 with ∑νγν=∞\sum_\nu\gamma^\nu=\infty∑ν​γν=∞, are the standard device of stochastic and distributed optimization: they need no line search, no function evaluations and no global information. For unconstrained or convex problems their convergence theory is classical. For nonconvex problems with nonconvex constraints it was missing:…

38 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear-Equality-Constrained Optimization with Rank-Deficient Jacobians: A Vanishing Merit Parameter Forces liminf ‖J_kᵀc_k‖ = 0Research Paper

Many problems in machine learning, optimal control and data-driven engineering design take the form of minimizing an expected loss f(x)=E[F(x,ι)]f(x) = \mathbb E[F(x,\iota)]f(x)=E[F(x,ι)] subject to deterministic nonlinear equality constraints c(x)=0c(x) = 0c(x)=0. When fff is an expectation over a large or unknown distribution, only stochastic gradient estimates gk≈∇f(xk)g_k \approx \nabla f(x_k)gk​≈∇f(xk​) are…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms VI: Predictor Directions Are O(μ) on the Optimal PartitionTextbook

Primal-dual interior-point methods for linear programming come with two kinds of guarantee. The worst-case one is a bound of O(nlog⁡(R/ϵ))O(\sqrt n\log(R/\epsilon))O(n​log(R/ϵ)) iterations to reduce the duality gap below ϵ\epsilonϵ. The asymptotic one says what happens to the duality gap near the end of the run, where practical codes spend their final iterations. For the…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms II: Proximity Measures and Newton Steps for the Analytic CenterTextbook

Interior-point methods for linear programming do not move along the boundary of the feasible region; they follow a curve of points that stay "central". The basic notion of centrality is the analytic center of a polytope, the interior point that maximizes the product of the slacks of its defining inequalities (Sonnevend, 1986, doi:10.1007/BFb0043914). Every…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Primal-Dual Interior-Point Methods V: Below a Threshold μ̄ the Projection Step Returns a Strictly Complementary SolutionTextbook

Primal-dual interior-point methods for linear programming generate strictly positive iterates that approach the solution set but never reach it: the duality measure μ\muμ tends to zero, yet no iterate is ever an exact solution. Many applications need more than an approximate point — an exact optimal basis, a vertex, or the optimal partition of the variables…

9 thms2 active usersReviewed
PreviousPage 6 of 11Next

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