More Like this

1. Parameter Selection by GCV and a \(\boldsymbol {\chi^2}\) Test within Iterative Methods for \(\boldsymbol{\ell_1}\)-Regularized Inverse Problems

   https://doi.org/10.1137/24M165805X  

   Sweeney, Brian; Renaut, Rosemary; Español, Malena I (May 2025, SIAM Journal on Scientific Computing)

   l1 regularization is used to preserve edges or enforce sparsity in a solution to an inverse problem. We investigate the split Bregman and the majorization-minimization iterative methods that turn this nonsmooth minimization problem into a sequence of steps that include solving an -regularized minimization problem. We consider selecting the regularization parameter in the inner generalized Tikhonov regularization problems that occur at each iteration in these iterative methods. The generalized cross validation method and chi2 degrees of freedom test are extended to these inner problems. In particular, for the chi2 test this includes extending the result for problems in which the regularization operator has more rows than columns and showing how to use the -weighted generalized inverse to estimate prior information at each inner iteration. Numerical experiments for image deblurring problems demonstrate that it is more effective to select the regularization parameter automatically within the iterative schemes than to keep it fixed for all iterations. Moreover, an appropriate regularization parameter can be estimated in the early iterations and fixed to convergence. 

   more » « less
2. On approximability of satisfiable $$\boldsymbol {k}$$-CSPs: II

   https://doi.org/10.1017/S0963548325100114  

   Bhangale, Amey; Khot, Subhash; Minzer, Dor (November 2025, Combinatorics, Probability and Computing)

   Abstract Let$$\Sigma$$be an alphabet and$$\mu$$be a distribution on$$\Sigma ^k$$for some$$k \geqslant 2$$. Let$$\alpha \gt 0$$be the minimum probability of a tuple in the support of$$\mu$$(denoted$$\mathsf{supp}(\mu )$$). We treat the parameters$$\Sigma , k, \mu , \alpha$$as fixed and constant. We say that the distribution$$\mu$$has a linear embedding if there exist an Abelian group$$G$$(with the identity element$$0_G$$) and mappings$$\sigma _i : \Sigma \rightarrow G$$,$$1 \leqslant i \leqslant k$$, such that at least one of the mappings is non-constant and for every$$(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$$,$$\sum _{i=1}^k \sigma _i(a_i) = 0_G$$. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let$$f_i: \Sigma ^n\rightarrow [\!-1,1]$$be bounded functions, such that at least one of the functions$$f_i$$essentially has degree at least$$d$$, meaning that the Fourier mass of$$f_i$$on terms of degree less than$$d$$is at most$$\delta$$. If$$\mu$$has no linear embedding (over any Abelian group), then is it necessarily the case that\begin{equation*}\left | \mathop {\mathbb{E}}_{({\textbf {x}}_1, {\textbf {x}}_2, \ldots , {\textbf {x}}_k)\sim \mu ^{\otimes n}}[f_1({\textbf {x}}_1)f_2({\textbf {x}}_2)\cdots f_k({\textbf {x}}_k)] \right | = o_{d, \delta }(1),\end{equation*}where the right hand side$$\to 0$$as the degree$$d \to \infty$$and$$\delta \to 0$$? In this paper, we answer this analytical question fully and in the affirmative for$$k=3$$. We also show the following two applications of the result.1.The first application is related to hardness of approximation. Using the reduction from [5], we show that for every$$3$$-ary predicate$$P:\Sigma ^3 \to \{0,1\}$$such that$$P$$has no linear embedding, anSDP (semi-definite programming) integrality gap instanceof a$$P$$-Constraint Satisfaction Problem (CSP) instance with gap$$(1,s)$$can be translated into a dictatorship test with completeness$$1$$and soundness$$s+o(1)$$, under certain additional conditions on the instance.2.The second application is related to additive combinatorics. We show that if the distribution$$\mu$$on$$\Sigma ^3$$has no linear embedding, marginals of$$\mu$$are uniform on$$\Sigma$$, and$$(a,a,a)\in \texttt{supp}(\mu )$$for every$$a\in \Sigma$$, then every large enough subset of$$\Sigma ^n$$contains a triple$$({\textbf {x}}_1, {\textbf {x}}_2,{\textbf {x}}_3)$$from$$\mu ^{\otimes n}$$(and in fact a significant density of such triples). 

   more » « less
3. KSB stability is automatic in codimension $$\boldsymbol{\geq 3}$$

   https://doi.org/10.1112/mod.2024.8  

   Kollár, János; Kovács, Sándor J (January 2024, Moduli)

   Abstract KSB stability holds at codimension$$1$$points trivially, and it is quite well understood at codimension$$2$$points because we have a complete classification of$$2$$-dimensional slc singularities. We show that it is automatic in codimension$$3$$. 

   more » « less
4. Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning

   https://doi.org/10.1137/22M1499261  

   Chen, Zaiwei; Clarke, John-Paul; Maguluri, Siva Theja (December 2023, SIAM Journal on Mathematics of Data Science)
5. \(\boldsymbol{\mathcal{L}_2}\)-Optimal Reduced-Order Modeling Using Parameter-Separable Forms

   https://doi.org/10.1137/22M1500678  

   Mlinarić, Petar; Gugercin, Serkan (April 2023, SIAM Journal on Scientific Computing)