Sparse trace norm regularization

We study the problem of estimating multiple predictive functions from a dictionary of basis functions in the nonparametric regression setting. Our estimation scheme assumes that each predictive function can be estimated in the form of a linear combination of the basis functions. By assuming that the coefficient matrix admits a sparse low-rank structure, we formulate the function estimation problem as a convex program regularized by the trace norm and the \(\ell _1\) -norm simultaneously. We propose to solve the convex program using the accelerated gradient (AG) method; we also develop efficient algorithms to solve the key components in AG. In addition, we conduct theoretical analysis on the proposed function estimation scheme: we derive a key property of the optimal solution to the convex program; based on an assumption on the basis functions, we establish a performance bound of the proposed function estimation scheme (via the composite regularization). Simulation studies demonstrate the effectiveness and efficiency of the proposed algorithms.     

Short communication: Dimensionality reduction of curvelet sparse regularizations in limited angle tomography

We investigate the reconstruction problem for limited angle tomography. Such problems arise naturally in applications like digital breast tomosynthesis, dental tomography, etc. Since the acquired tomographic data is highly incomplete, the reconstruction problem is severely ill-posed and the traditional reconstruction methods, such as filtered backprojection (FBP), do not perform well in such situations. To stabilize the inversion we propose the use of a sparse regularization technique in combination with curvelets. We argue that this technique has the ability to preserve edges. As our main result, we present a characterization of the kernel of the limited angle Radon transform in terms of curvelets. Moreover, we characterize reconstructions which are obtained via curvelet sparse regularizations at a limited angular range. As a result, we show that the dimension of the limited angle problem can be significantly reduced in the curvelet domain. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inversion of the X-ray transform from limited angle parallel beam region of interest data with applications to electron tomography

We present a new local tomographic algorithm applicable to electron microscopy tomography. Our algorithm applies to the standard data acquisition method, single-axis tilting, as well as for more arbitrary acquisition methods. Using microlocal analysis we put the reconstructions in a mathematical context, explaining which singularities are stably visible from the limited data given by the data collection protocol in the electron microscope. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Discrete tomography for reconstruction from limited view angles in non-destructive testing

We show that discrete tomography (DT) is suitable to increase the possible inspection size of single material oblong objects compared to filtered back projection (FBP) in non-destructive testing (NDT) with 2D X-ray computed tomography (CT). For such objects which are in one dimension larger than the maximum detectable material thickness limited view angles occur and FBP is not suitable for reconstruction. For evaluation of the reconstruction performance a copper phantom (strong absorber) which exhibits typical problems for NDT was manufactured. The increase of the object size with DT reconstruction compared to FBP was estimated to be above 50%.     

Reducing negative effects of quadratic norm regularization on image reconstruction in electrical impedance tomography

Employing the conventional quadratic norm to regularize the inverse problem in electrical impedance tomography often stabilizes the solution at the expense of imposing some smoothness on the reconstructed image. This study proposes a novel multi-regularized approach in order for quadratic norm regularization to reduce its deleterious effects on the reconstructed image. The amounts of regularization exerted on the finite elements over the mesh are not kept constant, but are changed depending on either the sensitivity of the boundary measurements to the finite elements, or the anomaly positioning. The results show that the proposed schemes appreciably improve the image with regard to spatial resolution, artifact, and shape preservation. These schemes considerably reduce the unappealing sensitivity of the inverse solution to the regularization parameter changes as well.     

Updating the regularization parameter in the adaptive cubic regularization algorithm

The adaptive cubic regularization method (Cartis et al. in Math. Program. Ser. A 127(2):245?C295, 2011; Math. Program. Ser. A. 130(2):295?C319, 2011) has been recently proposed for solving unconstrained minimization problems. At each iteration of this method, the objective function is replaced by a cubic approximation which comprises an adaptive regularization parameter whose role is related to the local Lipschitz constant of the objective??s Hessian. We present new updating strategies for this parameter based on interpolation techniques, which improve the overall numerical performance of the algorithm. Numerical experiments on large nonlinear least-squares problems are provided.     

L1 regularization method in electrical impedance tomography by using the L1-curve (Pareto frontier curve)

Electrical impedance tomography (EIT), as an inverse problem, aims to calculate the internal conductivity distribution at the interior of an object from current-voltage measurements on its boundary. Many inverse problems are ill-posed, since the measurement data are limited and imperfect. To overcome ill-posedness in EIT, two main types of regularization techniques are widely used. One is categorized as the projection methods, such as truncated singular value decomposition (SVD or TSVD). The other categorized as penalty methods, such as Tikhonov regularization, and total variation methods. For both of these methods, a good regularization parameter should yield a fair balance between the perturbation error and regularized solution. In this paper a new method combining the least absolute shrinkage and selection operator (LASSO) and the basis pursuit denoising (BPDN) is introduced for EIT. For choosing the optimum regularization we use the L1-curve (Pareto frontier curve) which is similar to the L-curve used in optimising L2-norm problems. In the L1-curve we use the L1-norm of the solution instead of the L2 norm. The results are compared with the TSVD regularization method where the best regularization parameters are selected by observing the Picard condition and minimizing generalized cross validation (GCV) function. We show that this method yields a good regularization parameter corresponding to a regularized solution. Also, in situations where little is known about the noise level σ, it is also useful to visualize the L1-curve in order to understand the trade-offs between the norms of the residual and the solution. This method gives us a means to control the sparsity and filtering of the ill-posed EIT problem. Tracing this curve for the optimum solution can decrease the number of iterations by three times in comparison with using LASSO or BPDN separately.     

Renormalization without regularization

A short review of recently developed renormalization schemes without regularization is presented. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 117, No. 2, pp 330–336, November, 1998.     

Multi-penalty regularization in learning theory

In this paper we establish the error estimates for multi-penalty regularization under the general smoothness assumption in the context of learning theory. One of the motivation for this work is to study the convergence analysis of two-parameter regularization theoretically in the manifold learning setting. In this spirit, we obtain the error bounds for the manifold learning problem using more general framework of multi-penalty regularization. We propose a new parameter choice rule “the balanced-discrepancy principle” and analyze the convergence of the scheme with the help of estimated error bounds. We show that multi-penalty regularization with the proposed parameter choice exhibits the convergence rates similar to single-penalty regularization. Finally on a series of test samples we demonstrate the superiority of multi-parameter regularization over single-penalty regularization.     

Elastic-net regularization in learning theory

Within the framework of statistical learning theory we analyze in detail the so-called elastic-net regularization scheme proposed by Zou and Hastie [H. Zou, T. Hastie, Regularization and variable selection via the elastic net, J. R. Stat. Soc. Ser. B, 67(2) (2005) 301–320] for the selection of groups of correlated variables. To investigate the statistical properties of this scheme and in particular its consistency properties, we set up a suitable mathematical framework. Our setting is random-design regression where we allow the response variable to be vector-valued and we consider prediction functions which are linear combinations of elements (features) in an infinite-dimensional dictionary. Under the assumption that the regression function admits a sparse representation on the dictionary, we prove that there exists a particular “elastic-net representation” of the regression function such that, if the number of data increases, the elastic-net estimator is consistent not only for prediction but also for variable/feature selection. Our results include finite-sample bounds and an adaptive scheme to select the regularization parameter. Moreover, using convex analysis tools, we derive an iterative thresholding algorithm for computing the elastic-net solution which is different from the optimization procedure originally proposed in the above-cited work.     

Concerning Kustaanheimo-Stiefel's regularization

Résumé Les équations du problème des deux corps, telles qu'elles ont été régularisées parKustaanheimo etStiefel, peuvent être résolues en forme universelle valable pour tous les genres d'orbites képlériennes. Ramenée aux coordonnées cartésiennes de départ, la solution ainsi exprimée se réduit aux formules deStumpff.     

Sparse Regression by Projection and Sparse Discriminant Analysis

Recent years have seen active developments of various penalized regression methods, such as LASSO and elastic net, to analyze high-dimensional data. In these approaches, the direction and length of the regression coefficients are determined simultaneously. Due to the introduction of penalties, the length of the estimates can be far from being optimal for accurate predictions. We introduce a new framework, regression by projection, and its sparse version to analyze high-dimensional data. The unique nature of this framework is that the directions of the regression coefficients are inferred first, and the lengths and the tuning parameters are determined by a cross-validation procedure to achieve the largest prediction accuracy. We provide a theoretical result for simultaneous model selection consistency and parameter estimation consistency of our method in high dimension. This new framework is then generalized such that it can be applied to principal components analysis, partial least squares, and canonical correlation analysis. We also adapt this framework for discriminant analysis. Compared with the existing methods, where there is relatively little control of the dependency among the sparse components, our method can control the relationships among the components. We present efficient algorithms and related theory for solving the sparse regression by projection problem. Based on extensive simulations and real data analysis, we demonstrate that our method achieves good predictive performance and variable selection in the regression setting, and the ability to control relationships between the sparse components leads to more accurate classification. In supplementary materials available online, the details of the algorithms and theoretical proofs, and R codes for all simulation studies are provided.     

Sparse matrices

One gives a survey of methods and programs for solving large sparse spectral problems based on the Lanczos algorithm. Practically all the important works on this topic are reflected in this survey. One also considers applications of the variants of the Lanczos method to the solution of symmetric indefinite systems of linear equations and to a series of other problems of linear algebra.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 20, pp. 179–260, 1982.     

On regularization in multiparameter eigenvalue problems

We consider the computation of simple and multiple eigenvalues and the corresponding eigenelements of a multiparameter eigenvalue problem in the sense of Atkinson by the reduction pseudoperturbation method. Namely, we regularize the original operator functions by finite-dimensional linear operators, thus reducing the case of multiple eigenvalues to that of simple ones.