Iterative reweighted methods for $$\ell _1-\ell _p$$ minimization

In this paper, we focus on the \(\ell _1-\ell _p\) minimization problem with \(0<p<1\), which is challenging due to the \(\ell _p\) norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of \(\ell _1-\ell _p\) minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous \(\epsilon \)-approximation to \(\ell _p\) norm, we design several iterative reweighted \(\ell _1\) and \(\ell _2\) methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of \(\ell _1-\ell _p\) minimization. This result, in particular, applies to the iterative reweighted \(\ell _1\) methods based on the new Lipschitz continuous \(\epsilon \)-approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter \(\epsilon \) is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods.     

Sharp MSE Bounds for Proximal Denoising

Denoising has to do with estimating a signal \(\mathbf {x}_0\) from its noisy observations \(\mathbf {y}=\mathbf {x}_0+\mathbf {z}\). In this paper, we focus on the “structured denoising problem,” where the signal \(\mathbf {x}_0\) possesses a certain structure and \(\mathbf {z}\) has independent normally distributed entries with mean zero and variance \(\sigma ^2\). We employ a structure-inducing convex function \(f(\cdot )\) and solve \(\min _\mathbf {x}\{\frac{1}{2}\Vert \mathbf {y}-\mathbf {x}\Vert _2^2+\sigma {\lambda }f(\mathbf {x})\}\) to estimate \(\mathbf {x}_0\), for some \(\lambda >0\). Common choices for \(f(\cdot )\) include the \(\ell _1\) norm for sparse vectors, the \(\ell _1-\ell _2\) norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate \(\mathbf {x}^*\) is the normalized mean-squared error \(\text {NMSE}(\sigma )=\frac{{\mathbb {E}}\Vert \mathbf {x}^*-\mathbf {x}_0\Vert _2^2}{\sigma ^2}\). We show that NMSE is maximized as \(\sigma \rightarrow 0\) and we find the exact worst-case NMSE, which has a simple geometric interpretation: the mean-squared distance of a standard normal vector to the \({\lambda }\)-scaled subdifferential \({\lambda }\partial f(\mathbf {x}_0)\). When \({\lambda }\) is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-\mathbf {x}\Vert _2\}\). The paper also connects these results to the generalized LASSO problem, in which one solves \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-{\mathbf {A}}\mathbf {x}\Vert _2\}\) to estimate \(\mathbf {x}_0\) from noisy linear observations \(\mathbf {y}={\mathbf {A}}\mathbf {x}_0+\mathbf {z}\). We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a “phase transition” as a function of number of observations. We also provide an order-optimal bound for the LASSO error in terms of the mean-squared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems.     

Amenability,critical exponents of subgroups and growth of closed geodesics

Let \(\Gamma \) be a (non-elementary) convex co-compact group of isometries of a pinched Hadamard manifold X. We show that a normal subgroup \(\Gamma _0\) has critical exponent equal to the critical exponent of \(\Gamma \) if and only if \(\Gamma /\Gamma _0\) is amenable. We prove a similar result for the exponential growth rate of closed geodesics on \(X/\Gamma \). These statements are analogues of classical results of Kesten for random walks on groups and Brooks for the spectrum of the Laplacian on covers of Riemannian manifolds.     

Data filtering for cluster analysis by $$\ell _0$$-norm regularization

A data filtering method for cluster analysis is proposed, based on minimizing a least squares function with a weighted \(\ell _0\)-norm penalty. To overcome the discontinuity of the objective function, smooth non-convex functions are employed to approximate the \(\ell _0\)-norm. The convergence of the global minimum points of the approximating problems towards global minimum points of the original problem is stated. The proposed method also exploits a suitable technique to choose the penalty parameter. Numerical results on synthetic and real data sets are finally provided, showing how some existing clustering methods can take advantages from the proposed filtering strategy.     

Normes cyclotomiques naïves et unités logarithmiques

We compute the \({\mathbb {Z}}\)-rank of the subgroup \(\widetilde{E}_K =\bigcap _{n\in {\mathbb {N}}} N_{K_n/K}(K_n^\times )\) of elements of the multiplicative group of a number field K that are norms from every finite level of the cyclotomic \({\mathbb {Z}}_\ell \)-extension \(K^c\) of K. Thus we compare its \(\ell \)-adification \({\mathbb {Z}}_\ell \otimes _{\mathbb {Z}}\widetilde{E}_K\) with the group of logarithmic units \(\widetilde{\varepsilon }_K\). By the way we point out an easy proof of the Gross–Kuz’min conjecture for \(\ell \)-undecomposed extensions of abelian fields.     

$$L^p$$ Joint Eigenfunction Bounds on Quaternionic Spheres

We prove some sharp \(L^p-L^2\) estimates for joint spectral projections \(\pi _{\ell \ell '}\), with \(\ell ,\ell '\in {\mathbb {N}}\), \(\ell \ge \ell '\ge 0\), \(1\le p\le 2\), associated to the Laplace–Beltrami operator and to a suitably defined subLaplacian on the unit quaternionic sphere.     

Isoperimetric problem for exponential measure on the plane with $$\ell _1$$-metric

We give a solution to the isoperimetric problem for the exponential measure on the plane with the \(\ell _1\)-metric. As it turns out, among all sets of a given measure, the simplex or its complement (i.e. the ball in the \(\ell _1\)-metric or its complement) has the smallest boundary measure. The proof is based on a symmetrisation (along the sections of equal \(\ell _1\)-distance from the origin).     

Second-order orthant-based methods with enriched Hessian information for sparse $$\ell _1$$-optimization

We present a second order algorithm, based on orthantwise directions, for solving optimization problems involving the sparsity enhancing \(\ell _1\)-norm. The main idea of our method consists in modifying the descent orthantwise directions by using second order information both of the regular term and (in weak sense) of the \(\ell _1\)-norm. The weak second order information behind the \(\ell _1\)-term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identification of the active set. We also prove that a reduced version of our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a specific choice of the algorithm parameters. We present several computational experiments to show the efficiency of our approach compared to other state-of-the-art algorithms.     

Domain variations and moving boundary problems

In the past few decades maximal regularity theory has successfully been applied to moving boundary problems. The basic idea is to reduce the system with varying domains to one in a fixed domain. This is done by a transformation, the so-called Hanzawa transformation, and yields a typically nonlocal and nonlinear coupled system of (evolution) equations. Well-posedness results can then often be established as soon as it is proved that the relevant linearization is the generator of an analytic semigroup or admits maximal regularity. To implement this program, it is necessary to somehow parametrize to space of boundaries/domains (typically the space of compact hypersurfaces \(\Gamma \) in \({\mathbb {R}}^n\), in the Euclidean setting). This has traditionally been achieved by means of the already mentioned Hanzawa transformation. The approach, while successful, requires the introduction of a smooth manifold \(\Gamma _\infty \) close to the manifold \(\Gamma _0\) in which one cares to linearize. This prevents one to use coordinates in which \(\Gamma _0\) lies at their “center”. As a result formulæ tend to contain terms that would otherwise not be present were one able to linearize in a neighborhood emanating from \(\Gamma _0\) instead of from \(\Gamma _\infty \). In this paper it is made use of flows (curves of diffeomorphisms) to obtain a general form of the relevant linearization in combination with an alternative coordinatization of the manifold of hypersurfaces, which circumvents the need for the introduction of a “phantom” reference manifold \(\Gamma _\infty \) by, in its place, making use of a “phantom geometry” on \(\Gamma _0\). The upshot is a clear insight into the structure of the linearization, simplified calculations, and simpler formulæ for the resulting linear operators, which are useful in applications.     

Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.     

Stable Signal Recovery from Phaseless Measurements

The aim of this paper is to study the stability of the \(\ell _1\) minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that \(m={\mathcal {O}}(k\log (N/k))\) measurements are enough to guarantee the \(\ell _1\) minimization to recover k-sparse signals stably provided the measurement matrix A satisfies the strong RIP property. We second investigate the phaseless instance-optimality presenting a null space property of the measurement matrix A under which there exists a decoder \(\Delta \) so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the \(\ell _1\) norm. This builds a parallel for compressive phase retrieval with the classical compressive sensing.     

Directed strongly walk-regular graphs

We generalize the concept of strong walk-regularity to directed graphs. We call a digraph strongly \(\ell \)-walk-regular with \(\ell > 1\) if the number of walks of length \(\ell \) from a vertex to another vertex depends only on whether the first vertex is the same as, adjacent to, or not adjacent to the second vertex. This generalizes also the well-studied strongly regular digraphs and a problem posed by Hoffman. Our main tools are eigenvalue methods. The case that the adjacency matrix is diagonalizable with only real eigenvalues resembles the undirected case. We show that a digraph \(\varGamma \) with only real eigenvalues whose adjacency matrix is not diagonalizable has at most two values of \(\ell \) for which \(\varGamma \) can be strongly \(\ell \)-walk-regular, and we also construct examples of such strongly walk-regular digraphs. We also consider digraphs with non-real eigenvalues. We give such examples and characterize those digraphs \(\varGamma \) for which there are infinitely many \(\ell \) for which \(\varGamma \) is strongly \(\ell \)-walk-regular.     

Congruences for $$\ell $$-regular overpartitions and Andrews’ singular overpartitions

Let \(\overline{A}_{\ell }(n)\) be the number of overpartitions of n into parts not divisible by \(\ell \). In a recent paper, Shen calls the overpartitions enumerated by the function \(\overline{A}_{\ell }(n)\) as \(\ell \)-regular overpartitions. In this paper, we find certain congruences for \(\overline{A}_{\ell }(n)\), when \(\ell =4, 8\), and 9. Recently, Andrews introduced the partition function \(\overline{C}_{k, i}(n)\), called singular overpartition, which counts the number of overpartitions of n in which no part is divisible by k and only parts \(\equiv \pm i\pmod {k}\) may be over-lined. He also proved that \(\overline{C}_{3, 1}(9n+3)\) and \(\overline{C}_{3, 1}(9n+6)\) are divisible by 3. In this paper, we prove that \(\overline{C}_{3, 1}(12n+11)\) is divisible by 144 which was conjectured to be true by Naika and Gireesh.     

Quadratic programs with hollows

Let \(\mathcal {F}\) be a quadratically constrained, possibly nonconvex, bounded set, and let \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) denote ellipsoids contained in \(\mathcal {F}\) with non-intersecting interiors. We prove that minimizing an arbitrary quadratic \(q(\cdot )\) over \(\mathcal {G}:= \mathcal {F}{\setminus } \cup _{k=1}^\ell {{\mathrm{int}}}(\mathcal {E}_k)\) is no more difficult than minimizing \(q(\cdot )\) over \(\mathcal {F}\) in the following sense: if a given semidefinite-programming (SDP) relaxation for \(\min \{ q(x) : x \in \mathcal {F}\}\) is tight, then the addition of l linear constraints derived from \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) yields a tight SDP relaxation for \(\min \{ q(x) : x \in \mathcal {G}\}\). We also prove that the convex hull of \(\{ (x,xx^T) : x \in \mathcal {G}\}\) equals the intersection of the convex hull of \(\{ (x,xx^T) : x \in \mathcal {F}\}\) with the same l linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.     

Absolute continuity and singularity of Palm measures of the Ginibre point process

We prove a dichotomy between absolute continuity and singularity of the Ginibre point process \(\mathsf {G}\) and its reduced Palm measures \(\{\mathsf {G}_{\mathbf {x}}, \mathbf {x} \in \mathbb {C}^{\ell }, \ell = 0,1,2\ldots \}\), namely, reduced Palm measures \(\mathsf {G}_{\mathbf {x}}\) and \(\mathsf {G}_{\mathbf {y}}\) for \(\mathbf {x} \in \mathbb {C}^{\ell }\) and \(\mathbf {y} \in \mathbb {C}^{n}\) are mutually absolutely continuous if and only if \(\ell = n\); they are singular each other if and only if \(\ell \not = n\). Furthermore, we give an explicit expression of the Radon–Nikodym density \(d\mathsf {G}_{\mathbf {x}}/d \mathsf {G}_{\mathbf {y}}\) for \(\mathbf {x}, \mathbf {y} \in \mathbb {C}^{\ell }\).     

The solution gap of the Brezis–Nirenberg problem on the hyperbolic space

We consider the positive solutions of the nonlinear eigenvalue problem \(-\Delta _{\mathbb {H}^n} u = \lambda u + u^p, \) with \(p=\frac{n+2}{n-2}\) and \(u \in H_0^1(\Omega ),\) where \(\Omega \) is a geodesic ball of radius \(\theta _1\) on \(\mathbb {H}^n.\) For radial solutions, this equation can be written as an ordinary differential equation having n as a parameter. In this setting, the problem can be extended to consider real values of n. We show that if \(2<n<4\) this problem has a unique positive solution if and only if \(\lambda \in \left( n(n-2)/4 +L^*\,,\, \lambda _1\right) .\) Here \(L^*\) is the first positive value of \(L = -\ell (\ell +1)\) for which a suitably defined associated Legendre function \(P_{\ell }^{-\alpha }(\cosh \theta ) >0\) if \(0 < \theta <\theta _1\) and \(P_{\ell }^{-\alpha }(\cosh \theta _1)=0,\) with \(\alpha = (2-n)/2\).     

On some constacyclic codes over $$\mathbb {Z}_{4}\left[ u\right] /\left\langle u^{2}-1\right\rangle $$, their $$\mathbb {Z}_4$$Z4 images,and new codes

In this paper, we study \(\lambda \)-constacyclic codes over the ring \(R=\mathbb {Z}_4+u\mathbb {Z}_4\) where \(u^{2}=1\), for \(\lambda =3+2u\) and \(2+3u\). Two new Gray maps from R to \(\mathbb {Z}_4^{3}\) are defined with the goal of obtaining new linear codes over \(\mathbb {Z}_4\). The Gray images of \(\lambda \)-constacyclic codes over R are determined. We then conducted a computer search and obtained many \(\lambda \)-constacyclic codes over R whose \(\mathbb {Z}_4\)-images have better parameters than currently best-known linear codes over \(\mathbb {Z}_4\).     

New congruences for $$\ell $$-regular partitions for $$\ell \in \{5,6,7,49\}$$∈{5,6,7,49}

We find several new congruences for \(\ell \)-regular partitions for \(\ell \in \{5,6,7,49\}\) and also find alternative proofs of the congruences for 10- and 20-regular partitions which were proved earlier by Carlson and Webb (Ramanujan J 33:329–337, 2014) by using the theory of modular forms. We use certain p-dissections of \((q;q)_{\infty }\), \(\psi (q)\), \((q;q)_{\infty }^3\) and \(\psi (q^2)(q;q)_{\infty }^2\).     

The Raising Steps Method: Applications to the $$\bar{\partial }$$ Equation in Stein Manifolds

In order to have estimates on the solutions of the equation \(\bar{\partial }u=\omega \) on a Stein manifold, we introduce a new method, the “raising steps method”, to get global results from local ones. In particular, it allows us to transfer results from open sets in \({\mathbb {C}}^{n}\) to open sets in a Stein manifold. Using it, we get \(\displaystyle L^{r}-L^{s}\) results for solutions of the equation \(\bar{\partial }u=\omega \) with a gain, \(\displaystyle s>r\), in strictly pseudo convex domains in Stein manifolds. We also get \(\displaystyle L^{r}-L^{s}\) results for domains in \({\mathbb {C}}^{n}\) locally biholomorphic to convex domains of finite type.     

Slope instability of projective spaces blown up along a line

Let \(\text {Bl}_{\mathbb {P}^1} \mathbb {P}^n\) be a Kähler manifold obtained by blowing up a complex projective space \(\mathbb {P}^n\) along a line \(\mathbb {P}^1\). We prove that \(\text {Bl}_{\mathbb {P}^1} \mathbb {P}^n\) is slope unstable with respect to any polarisation, and hence, it does not admit constant scalar curvature Kähler metrics in any rational Kähler class.