We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the
This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “
- Award ID(s):
- 2006762
- NSF-PAR ID:
- 10411443
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Mathematical Programming
- Volume:
- 204
- Issue:
- 1-2
- ISSN:
- 0025-5610
- Format(s):
- Medium: X Size: p. 517-566
- Size(s):
- ["p. 517-566"]
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract -norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ -norm of solutions to systems$$\ell _0$$ , where$$A\varvec{x}=\varvec{b}$$ ,$$A\in \mathbb {Z}^{m\times n}$$ and$${\varvec{b}}\in \mathbb {Z}^m$$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\varvec{x}$$ -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\ell _0$$ , to other subdomains such as$$\mathbb {R}$$ . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.$$\mathbb {Z}$$ -
Abstract Sparsity finds applications in diverse areas such as statistics, machine learning, and signal processing. Computations over sparse structures are less complex compared to their dense counterparts and need less storage. This paper proposes a heuristic method for retrieving sparse approximate solutions of optimization problems via minimizing the
quasi-norm, where$$\ell _{p}$$ . An iterative two-block algorithm for minimizing the$$0 quasi-norm subject to convex constraints is proposed. The proposed algorithm requires solving for the roots of a scalar degree polynomial as opposed to applying a soft thresholding operator in the case of$$\ell _{p}$$ norm minimization. The algorithm’s merit relies on its ability to solve the$$\ell _{1}$$ quasi-norm minimization subject to any convex constraints set. For the specific case of constraints defined by differentiable functions with Lipschitz continuous gradient, a second, faster algorithm is proposed. Using a proximal gradient step, we mitigate the convex projection step and hence enhance the algorithm’s speed while proving its convergence. We present various applications where the proposed algorithm excels, namely, sparse signal reconstruction, system identification, and matrix completion. The results demonstrate the significant gains obtained by the proposed algorithm compared to other$$\ell _{p}$$ quasi-norm based methods presented in previous literature.$$\ell _{p}$$ -
Abstract Approximate integer programming is the following: For a given convex body
, either determine whether$$K \subseteq {\mathbb {R}}^n$$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ which is$$2\cdot (K - c) +c$$ K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ . So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$2^{O(n)} \cdot n^n$$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ , provided that the$$2^{O(n)}$$ remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ of$$\ell \ge 5(n+1)$$ are given. The algorithm is based on a$$x^*$$ cutting-plane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new$$2^{O(n)}n^n$$ asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ .$$n^n \cdot 2^{O(n)}$$ -
Abstract There are many ways of measuring and modeling tail-dependence in random vectors: from the general framework of multivariate regular variation and the flexible class of max-stable vectors down to simple and concise summary measures like the matrix of bivariate tail-dependence coefficients. This paper starts by providing a review of existing results from a unifying perspective, which highlights connections between extreme value theory and the theory of cuts and metrics. Our approach leads to some new findings in both areas with some applications to current topics in risk management.
We begin by using the framework of multivariate regular variation to show that extremal coefficients, or equivalently, the higher-order tail-dependence coefficients of a random vector can simply be understood in terms of random exceedance sets, which allows us to extend the notion of Bernoulli compatibility. In the special but important case of bivariate tail-dependence, we establish a correspondence between tail-dependence matrices and
- and$$L^1$$ -embeddable finite metric spaces via the spectral distance, which is a metric on the space of jointly 1-Fréchet random variables. Namely, the coefficients of the cut-decomposition of the spectral distance and of the Tawn-Molchanov max-stable model realizing the corresponding bivariate extremal dependence coincide. We show that line metrics are rigid and if the spectral distance corresponds to a line metric, the higher order tail-dependence is determined by the bivariate tail-dependence matrix.$$\ell _1$$ Finally, the correspondence between
-embeddable metric spaces and tail-dependence matrices allows us to revisit the realizability problem, i.e. checking whether a given matrix is a valid tail-dependence matrix. We confirm a conjecture of Shyamalkumar and Tao (2020) that this problem is NP-complete.$$\ell _1$$ -
We show that for primes
with , the class number of is divisible by . Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that when , there is always a cusp form of weight and level whose th Fourier coefficient is congruent to modulo a prime above , for all primes . We use the Galois representation of such a cusp form to explicitly construct an unramified degree- extension of .