Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn iterative support shrinking algorithm for $ell_{p}$-$ell_{q}$ minimization
43
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present an iterative support shrinking algorithm for $ell_{p}$-$ell_{q}$ minimization~($0 <p < 1 leq q < infty $). This algorithm guarantees the nonexpensiveness of the signal support set and can be easily implemented after being proximally linearized. The subproblem can be very efficiently solved due to its convexity and reducing size along iteration. We prove that the iterates of the algorithm globally converge to a stationary point of the $ell_{p}$-$ell_{q}$ objective function. In addition, we show a lower bound theory for the iteration sequence, which is more practical than the lower bound results for local minimizers in the literature.
rate research
Read More
In this paper we propose a primal-dual homotopy method for $ell_1$-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.
The Chebyshev or $ell_{infty}$ estimator is an unconventional alternative to the ordinary least squares in solving linear regressions. It is defined as the minimizer of the $ell_{infty}$ objective function begin{align*} hat{boldsymbol{beta}} := argmin_{boldsymbol{beta}} |boldsymbol{Y} - mathbf{X}boldsymbol{beta}|_{infty}. end{align*} The asymptotic distribution of the Chebyshev estimator under fixed number of covariates were recently studied (Knight, 2020), yet finite sample guarantees and generalizations to high-dimensional settings remain open. In this paper, we develop non-asymptotic upper bounds on the estimation error $|hat{boldsymbol{beta}}-boldsymbol{beta}^*|_2$ for a Chebyshev estimator $hat{boldsymbol{beta}}$, in a regression setting with uniformly distributed noise $varepsilon_isim U([-a,a])$ where $a$ is either known or unknown. With relatively mild assumptions on the (random) design matrix $mathbf{X}$, we can bound the error rate by $frac{C_p}{n}$ with high probability, for some constant $C_p$ depending on the dimension $p$ and the law of the design. Furthermore, we illustrate that there exist designs for which the Chebyshev estimator is (nearly) minimax optimal. In addition we show that Chebyshevs LASSO has advantages over the regular LASSO in high dimensional situations, provided that the noise is uniform. Specifically, we argue that it achieves a much faster rate of estimation under certain assumptions on the growth rate of the sparsity level and the ambient dimension with respect to the sample size.
The task of predicting missing entries of a matrix, from a subset of known entries, is known as textit{matrix completion}. In todays data-driven world, data completion is essential whether it is the main goal or a pre-processing step. Structured matrix completion includes any setting in which data is not missing uniformly at random. In recent work, a modification to the standard nuclear norm minimization (NNM) for matrix completion has been developed to take into account emph{sparsity-based} structure in the missing entries. This notion of structure is motivated in many settings including recommender systems, where the probability that an entry is observed depends on the value of the entry. We propose adjusting an Iteratively Reweighted Least Squares (IRLS) algorithm for low-rank matrix completion to take into account sparsity-based structure in the missing entries. We also present an iterative gradient-projection-based implementation of the algorithm that can handle large-scale matrices. Finally, we present a robust array of numerical experiments on matrices of varying sizes, ranks, and level of structure. We show that our proposed method is comparable with the adjusted NNM on small-sized matrices, and often outperforms the IRLS algorithm in structured settings on matrices up to size $1000 times 1000$.
Faraday tomography offers crucial information on the magnetized astronomical objects, such as quasars, galaxies, or galaxy clusters, by observing its magnetoionic media. The observed linear polarization spectrum is inverse Fourier transformed to obtain the Faraday dispersion function (FDF), providing us a tomographic distribution of the magnetoionic media along the line of sight. However, this transform gives a poor reconstruction of the FDF because of the instruments limited wavelength coverage. The current Faraday tomography techniques inability to reliably solve the above inverse problem has noticeably plagued cosmic magnetism studies. We propose a new algorithm inspired by the well-studied area of signal restoration, called the Constraining and Restoring iterative Algorithm for Faraday Tomography (CRAFT). This iterative model-independent algorithm is computationally inexpensive and only requires weak physically-motivated assumptions to produce high fidelity FDF reconstructions. We demonstrate an application for a realistic synthetic model FDF of the Milky Way, where CRAFT shows greater potential over other popular model-independent techniques. The dependence of observational frequency coverage on the various techniques reconstruction performance is also demonstrated for a simpler FDF. CRAFT exhibits improvements even over model-dependent techniques (i.e., QU-fitting) by capturing complex multi-scale features of the FDF amplitude and polarization angle variations within a source. The proposed approach will be of utmost importance for future cosmic magnetism studies, especially with broadband polarization data from the Square Kilometre Array and its precursors. We make the CRAFT code publicly available.
We propose an iterative algorithm for the minimization of a $ell_1$-norm penalized least squares functional, under additional linear constraints. The algorithm is fully explicit: it uses only matrix multiplications with the three matrices present in the problem (in the linear constraint, in the data misfit part and in penalty term of the functional). None of the three matrices must be invertible. Convergence is proven in a finite-dimensional setting. We apply the algorithm to a synthetic problem in magneto-encephalography where it is used for the reconstruction of divergence-free current densities subject to a sparsity promoting penalty on the wavelet coefficients of the current densities. We discuss the effects of imposing zero divergence and of imposing joint sparsity (of the vector components of the current density) on the current density reconstruction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
