Search

Nowadays, low-rank approximations are a critical component of many numerical procedures. Traditionally the problem of low-rank approximation of matrices is solved in unitary invariant norms such as Frobenius or spectral norm due to the existence of efficient methods for constructing approximations. However, recent results discover the potential of low-rank approximations in the Chebyshev norm, which naturally arises in many applications. In this paper, we investigate the problem of uniform approximation of vectors, which is the main component in the low-rank approximations of matrices in the Chebyshev norm. The principal novelty of this paper is the accelerated algorithm for solving uniform approximation problems. We also analyze the iterative procedure of the proposed algorithm and demonstrate that it has a geometric convergence rate. Finally, we provide an extensive numerical evaluation, which demonstrates the effectiveness of the proposed procedures. [ABSTRACT FROM AUTHOR]

Given a nonnegative matrix A=(Aij) , the matrix scaling problem asks whether A can be scaled to a doubly stochastic matrix D1AD2 for some positive diagonal matrices D1, D2. The Sinkhorn algorithm is a simple iterative algorithm, which repeats row-normalization Aij←Aij/∑jAij and column-normalization Aij←Aij/∑iAij alternatively. By this algorithm, A converges to a doubly stochastic matrix in limit if and only if the bipartite graph associated with A has a perfect matching. This property can decide the existence of a perfect matching in a given bipartite graph G, which is identified with the 0, 1-matrix AG. Linial et al. (2000) showed that O(n2log n) iterations for AG decide whether G has a perfect matching. Here, n is the number of vertices in one of the color classes of G. In this paper, we show an extension of this result. If G has no perfect matching, then a polynomial number of the Sinkhorn iterations identifies a Hall blocker—a vertex subset X having neighbors Γ(X) with |X|>|Γ(X)| , which is a certificate of the nonexistence of a perfect matching. Specifically, we show that O(n2log n) iterations can identify one Hall blocker and that further polynomial iterations can also identify all parametric Hall blockers X of maximizing (1−λ)|X|−λ|Γ(X)| for λ∈[0,1]. The former result is based on an interpretation of the Sinkhorn algorithm as alternating minimization for geometric programming. The latter is on an interpretation as alternating minimization for Kullback–Leibler (KL) divergence and on its limiting behavior for a nonscalable matrix. We also relate the Sinkhorn limit with parametric network flow, principal partition of polymatroids, and the Dulmage–Mendelsohn decomposition of a bipartite graph. Funding: K. Hayashi was supported by the Japan Society for the Promotion of Science [Grant JP19J22605]. H. Hirai was supported by Precursory Research for Embryonic Science and Technology [Grant JPMJPR192A]. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the factors of a rank- |$1$| matrix with i.i.d. Gaussian, rank- |$1$| measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this non-convex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic one-step recursion that is accurate even in high-dimensional problems. Notably, while the infinite-sample population update is uninformative and suggests exact recovery in a single step, the algorithm—and our deterministic one-step prediction—converges geometrically fast from a random initialization. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behaviour. On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic one-step updates within fluctuations of the order |$n^{-1/2}$| when each iteration is run with |$n$| observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional |$M$| -estimation and provides an avenue for sharply analyzing complex iterative algorithms from a random initialization in other high-dimensional optimization problems with random data. [ABSTRACT FROM AUTHOR]

For some typical and widely used non-convex half-quadratic regularization models and the Ambrosio-Tortorelli approximate Mumford-Shah model, based on the Kurdyka-Łojasiewicz analysis and the recent nonconvex proximal algorithms, we developed an efficient preconditioned framework aiming at the linear subproblems that appeared in the nonlinear alternating minimization procedure. Solving large-scale linear subproblems is always important and challenging for lots of alternating minimization algorithms. By incorporating the efficient and classical preconditioned iterations into the nonlinear and nonconvex optimization, we prove that only one or any finite times preconditioned iterations are needed for the linear subproblems without controlling the error as the usual inexact solvers. The proposed preconditioned framework in finite-dimensional space can provide great flexibility and efficiency for dealing with linear subproblems and guarantee global convergence for lots of nonlinear and nonconvex regularization models. [ABSTRACT FROM AUTHOR]

We focus on nonconvex and non-smooth block optimization problems, where the smooth coupling part of the objective does not satisfy a global/partial Lipschitz gradient continuity assumption. A general alternating minimization algorithm is proposed that combines two proximal-based steps, one classical and another with respect to the Bregman divergence. Combining different analytical techniques, we provide a complete analysis of the behavior—from global to local—of the algorithm, and show when the iterates converge globally to critical points with a locally linear rate for sufficiently regular (though not necessarily convex) objectives. Numerical experiments illustrate the theoretical findings. [ABSTRACT FROM AUTHOR]

Training deep neural networks (DNNs) is an important and challenging optimization problem in machine learning due to its non-convexity and non-separable structure. The alternating minimization (AM) approaches split the composition structure of DNNs and have drawn great interest in the deep learning and optimization communities. In this paper, we propose a unified framework for analyzing the convergence rate of AM-type network training methods. Our analysis is based on the non-monotone j-step sufficient decrease conditions and the Kurdyka-Łojasiewicz (KL) property, which relaxes the requirement of designing descent algorithms. We show the detailed local convergence rate if the KL exponent θ varies in [0, 1). Moreover, the local R-linear convergence is discussed under a stronger j-step sufficient decrease condition. [ABSTRACT FROM AUTHOR]

The practical implementation of massive multi-user multi-input–multi-output (MU-MIMO) downlink communication systems power amplifiers that are energy efficient; otherwise, the power consumption of the base station (BS) will be prohibitive. Constant envelope (CE) precoding is gaining increasing interest for its capability to utilize low-cost, high-efficiency nonlinear radio frequency amplifiers. Our work focuses on the topic of CE precoding in massive MU-MIMO systems and presents an efficient CE precoding algorithm. This algorithm uses an alternating minimization (AltMin) framework to optimize the CE precoded signal and precoding factor, aiming to minimize the difference between the received signal and the transmit symbol. For the optimization of the CE precoded signal, we provide a powerful approach that integrates the majorization-minimization (MM) method and the fast iterative shrinkage-thresholding (FISTA) method. This algorithm combines the characteristics of the massive MU-MIMO channel with the second-order Taylor expansion to construct the surrogate function in the MM method, in which minimizing this surrogate function is the worst-case of the system. Specifically, we expand the suggested CE precoding algorithm to involve the discrete constant envelope (DCE) precoding case. In addition, we thoroughly examine the exact property, convergence, and computational complexity of the proposed algorithm. Simulation results demonstrate that the proposed CE precoding algorithm can achievean uncoded biterror rate (BER) performance gain of roughly 1 dB compared to the existing CE precoding algorithm and has an acceptable computational complexity. This performance advantage also exists when it comes to DCE precoding. [ABSTRACT FROM AUTHOR]

Machine learning has developed rapidly and involves many fields, such as signal detection and biological research. However, systems may exist outliers caused by the malicious violation of the attacker during the learning process, which makes machine learning instable and unreliable. Therefore, building a trustworthy model to meet robustness has become an urgent research topic. In this paper, we propose the trustworthy regularized Huber regression by Huber loss and decomposable regularizer under the mean shift model, which can identify and eliminate impacts on outliers and heavy-tailed errors. We establish the consistency and convergence rate of the regularized Huber estimators. The asymptotic property of outliers support recovery is explored in term of false and true discovery rates. Then we design an efficient algorithm by combining the alternating minimization and accelerated proximal gradient method to solve the trustworthy regularized Huber regression. Finally, extensive comparisons on simulation and real datasets demonstrate the superior performances. [ABSTRACT FROM AUTHOR]

The main aim of this paper is to develop a histogram equalization algorithm for color image contrast enhancement. Our idea is to propose a variational approach containing an energy functional to determine local transformations in the lightness (L) and chroma (C) channels of the CIE LCH color space such that the histograms in these two channels can be redistributed locally. In order to minimize the differences among the local transformation at the nearby pixel locations in each channel, the spatial regularization of the transformation is incorporated in the functional for the equalization process. The existence and uniqueness of the minimizer of the variational model can be shown. Experimental results are reported to show that the performance of the proposed models is competitive with the other compared methods for several testing images. [ABSTRACT FROM AUTHOR]

In this article, we propose a variational approach for estimating the clean hyperspectral images (HSI) that are corrupted by the combined effect of Gaussian noise, impulse noise, stripes, and deadlines. Successful removal of noise from the corrupted observations is essential for subsequent downstream analyses like classification, spectral unmixing, and target tracking. The main contribution of this work is as follows. First, an objective function is designed for the joint estimation of clean data and impulse corrupted pixels. A rationale is presented for using the $\ell _{0}-$norm to estimate the exact sparsity induced by impulse noise. Second, the problem is reformulated as a multiconvex problem, which is solved using proximal projection and alternating minimization. Third, to exploit the spatial-spectral similarity, a nonlocal and vectorized version of total variation regularization is proposed to estimate the clean data. Lastly, a study on the parameter sensitivity analysis empirically validates the convergence of the restoration results under different values of the regularization hyperparameters. The experiments conducted over synthetically corrupted and real HSI data obtained from hyperspectral sensors suggest the potential utility of the proposed methodology (CompoHyDen) at a scalable level.

The problem of low rank approximation is ubiquitous in science. Traditionally this problem is solved in unitary invariant norms such as Frobenius or spectral norm due to existence of efficient methods for building approximations. However, recent results reveal the potential of low rank approximations in Chebyshev norm, which naturally arises in many applications. In this paper we tackle the problem of building optimal rank-1 approximations in the Chebyshev norm. We investigate the properties of alternating minimization algorithm for building the low rank approximations and demonstrate how to use it to construct optimal rank-1 approximation. As a result we propose an algorithm that is capable of building optimal rank-1 approximations in Chebyshev norm for moderate matrices. [ABSTRACT FROM AUTHOR]

Motivated by a recent framework for proving global convergence to critical points of nested alternating minimization algorithms, which was proposed for the case of smooth subproblems, we first show here that non-smooth subproblems can also be handled within this framework. Specifically, we present a novel analysis of an optimization scheme that utilizes the FISTA method as a nested algorithm. We establish the global convergence of this nested scheme to critical points of non-convex and non-smooth optimization problems. In addition, we propose a hybrid framework that allows to implement FISTA when applicable, while still maintaining the global convergence result. The power of nested algorithms using FISTA in the non-convex and non-smooth setting is illustrated with some numerical experiments that show their superiority over existing methods. [ABSTRACT FROM AUTHOR]

This paper proposes an inverse eigenstrain analysis procedure to estimate full-field residual stress from an incompletely measured residual elastic strain or stress field. The inverse problem is solved by minimizing the linear elastic constitutive relation discrepancy that arises from different admissible stress and strain fields within an alternating minimization framework. First, a standard forward thermoelastic problem is solved to obtain a statically admissible total strain field. Then, full-field residual stress (or elastic strain) that satisfies partial measurement is obtained by minimizing a Hellinger-Reissner-type energy functional under a mixed variational framework. We have used standard two and three-dimensional hybrid finite elements to obtain a stress field. Finally, a full-field eigenstrain field is obtained by minimizing constitutive disparity due to dissimilar elastic strain and total strain fields. We show the efficacy of the proposed procedure with some numerically obtained and experimentally reported data. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of nonconvex and nonsmooth optimization problems, whose objective function can be split into two separable terms and one coupling term. Alternating proximal gradient methods combining with extrapolation are proposed to solve such problems. Under some assumptions, we prove that every cluster point of the sequence generated by our algorithms is a critical point. Furthermore, if the objective function satisfies Kurdyka–Łojasiewicz property, the generated sequence is globally convergent to a critical point. In order to make the algorithm more effective and flexible, we also use some strategies to update the extrapolation parameter and solve the problems with unknown Lipschitz constant. Numerical experiments demonstrate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This paper develops a novel adaptive, augmented, Lagrangian-based method to address the comprehensive class of nonsmooth, nonconvex models with a nonlinear, functional composite structure in the objective. The proposed method uses an adaptive mechanism for the update of the feasibility penalizing elements, essentially turning our multiplier type method into a simple alternating minimization procedure based on the augmented Lagrangian function from some iteration onward. This allows us to avoid the restrictive and, until now, mandatory surjectivity-type assumptions on the model. We establish the iteration complexity of the proposed scheme to reach an ε-critical point. Moreover, we prove that the limit point of every bounded sequence generated by a procedure that employs the method with strictly decreasing levels of precision is a critical point of the problem. Our approach provides novel results even in the simpler composite linear model, in which the surjectivity of the linear operator is a baseline assumption. Funding: N. Hallak's research was partially supported by the Israel Science Foundation [Grant 637/21]. M. Teboulle's research was partially supported by the Israel Science Foundation [Grants 1844-16 and 2619-20]. [ABSTRACT FROM AUTHOR]

Copyright of Telecommunication Engineering is the property of Telecommunication Engineering and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Massive multiple-input-multiple-output (MIMO) is a key enabler for obtaining higher data rates in the next generation wireless technology. While it has the power to transform cellular communication, with potential for spatial diversity and multiplexing, a bottleneck that often gets overlooked is the fronthaul capacity. The fronthaul link that connects a massive MIMO Remote Radio Head (RRH) and carries in-phase and quadrature (IQ) samples to the Baseband Unit (BBU) of the base station can throttle the network capacity/speed if appropriate data compression techniques are not applied, particularly in the uplink. This paper proposes an iterative technique for fronthaul load reduction in the uplink for massive MIMO systems utilizing the convolution structure of the received signals. The proposed algorithm provides compression ratios of about 30- $50\times $ . This work provides extensive analysis of the performance of the proposed method for a plethora of practical scenarios and constraints, such as different channel parameters and models, receive antenna correlation, and under imperfect channel information. It also discusses the numerical convergence and complexity of the proposed algorithm and compares the performance against other existing compression techniques.

This paper considers a 1D time-domain inverse scattering problem for the Helmholtz equation in which penetrable scatterers are to be determined from boundary measurements of the scattering data. It is formulated as a coefficient identification problem for a wave equation. Using the Laplace transform, the inverse problem is converted into an overdetermined nonlinear system of partial differential equations. To solve this system, a Carleman weighted objective functional, which is proved to be strictly convex in an arbitrary set in a Hilbert space, is constructed. An alternating minimization algorithm is used to minimize the Carleman weighted objective functional. Numerical results are presented to illustrate the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A type of matrix decomposition called unilateral orthogonal nonnegative matrix factorization is proposed for decomposing real-valued matrices. The associated optimization problem is nonconvex and nonlinear. We design an iterative algorithm based on alternating minimization, where a data compensation mechanism is used to avoid ill-conditioned problems. We also show that there is an interesting connection between the iterative algorithm and switched nonlinear systems. By analyzing the switched systems, we prove that each iteration of the algorithm is rank-preserving and thus avoids ill-conditioned problems. The solution to the optimization problem is also strictly feasible without any approximations. The optimization variables are proved to be convergent, and the limit satisfies the Karush-Kuhn-Tucker conditions. Furthermore, it is proved that the limit is almost surely a local minimizer rather than a saddle point. For the equivalent switched systems, the states of all subsystems are convergent. [ABSTRACT FROM AUTHOR]

We propose a general inertial version of the proximal alternating linearized minimization (PALM) (denoted by NiPALM) for a class of nonconvex and nonsmooth minimization problems, whose objective function is the sum of a smooth function of the entire variables and two nonsmooth functions of each variable. NiPALM is general in the sense that it contains the popular PALM, the inertial PALM (iPALM) and Gauss-Seidel type inertial PALM (GiPALM) as special cases. Under mild assumptions, namely, the underlying functions satisfy the Kurdyka-Łojasiewicz (KL) property and some suitable conditions on the parameters, we prove that each bounded sequence generated by NiPALM globally converges to a critical point. We also apply NiPALM to nonnegative matrix factorization, sparse principal component analysis, and weighted low-rank matrix restoration problems. Comparing results with those by PALM, iPALM, and GiPALM demonstrate the robustness and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Ptychography is a lensless imaging technique, which considers reconstruction from a set of far-field diffraction patterns obtained by illuminating small overlapping regions of the specimen. In many cases, the distribution of light inside the illuminated region is unknown and has to be estimated along with the object of interest. This problem is referred to as blind ptychography. While in ptychography the illumination is commonly assumed to have a point spectrum, in this paper we consider an alternative scenario with a nontrivial light spectrum known as blind polychromatic ptychography. First, we show that nonblind polychromatic ptychography can be seen as a recovery from quadratic measurements. Then, a reconstruction from such measurements can be performed by a variant of the Amplitude Flow algorithm, which has guaranteed sublinear convergence to a critical point. Second, we address recovery from blind polychromatic ptychographic measurements by devising an alternating minimization version of Amplitude Flow and showing that it converges to a critical point at a sublinear rate. [ABSTRACT FROM AUTHOR]

Motivated by applications in image processing, we consider a class of structured convex optimization problems in which the objective function is the sum of two component functions with favorable structures, and, furthermore, both of which are composed with linear operators. In particular, to recover images degraded by Poisson noise, the famous Kullback-Leibler divergence can be adopted in data fitting, in which case one component function is separable, strongly convex and easy to minimize. The other component function usually allows an easily computable proximal operator. We then propose, analyze and test a hybrid algorithm particularly tailored for the underlying model structures, which can be viewed as a combination of the famous alternating minimization algorithm of Tseng and the alternating direction method of multipliers. Under mild conditions, global iterate convergence as well as ergodic $ \mathcal{O}(1/N) $ sublinear convergence rate results measured by the function value residual and constraint violation of a reformulated constrained optimization problem are established, where $ N $ denotes the iteration counter. The proposed algorithm is applied to fractional-order total variation regularized image denoising and deblurring problems, where the noise obeys Poisson distribution. Our experimental results demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

It is often challenging to selectively segment the images with intensity inhomogeneity for the existing region-based variational models. This article proposes a Retinex-based selective segmentation model for inhomogeneous images. The main idea is to employ the Retinex theory to decouple the input inhomogeneous image into illumination bias and reflective parts and then introduce the regularizer of these two parts in the proposed model for selective segmentation. Also, a convex formulation of the model is presented and the relationship between the solutions of the proposed model and its convex relaxation is given. Furthermore, we design an effective algorithm for numerically solving the model by incorporating the alternating minimization method. Experimental results on synthetic binary images and real medical images validate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

Mask-based lensless cameras replace the lens of a conventional camera with a custom mask. These cameras can potentially be very thin and even flexible. Recently, it has been demonstrated that such mask-based cameras can recover light intensity and depth information of a scene. Existing depth recovery algorithms either assume that the scene consists of a small number of depth planes or solve a sparse recovery problem over a large 3D volume. Both these approaches fail to recover the scenes with large depth variations. In this paper, we propose a new approach for depth estimation based on an alternating gradient descent algorithm that jointly estimates a continuous depth map and light distribution of the unknown scene from its lensless measurements. We present simulation results on image and depth reconstruction for a variety of 3D test scenes. A comparison between the proposed algorithm and other method shows that our algorithm is more robust for natural scenes with a large range of depths. We built a prototype lensless camera and present experimental results for reconstruction of intensity and depth maps of different real objects.

In mm-wave massive Multiple Input Multiple Output (MIMO) systems, in order to further improve the spectral efficiency of hybrid precoding in fully connected structure, an Alternate Minimization based on Gradient Descent (GD-AltMin) hybrid precoding algorithm is proposed. Firstly, the right singular vector of the channel matrix is used to initialize the analog precoding matrix. Secondly, digital and analog precoding matrices are updated by least square criterion and gradient descent method respectively. Then, under the principle of alternating minimization, the digital and analog precoding matrices are updated iteratively until the optimal digital and analog precoding matrices are obtained. Through theoretical analysis and numerical simulation, the spectral efficiency of several classical algorithms are compared under different signal-to-noise-ratio, number of radio frequency links and number of transmitting antennas. The results show that the spectral efficiency of the proposed algorithm is closer to the optimal unconstrained precoding algorithm than alternate minimization algorithm using phase extraction and channel singular value decomposition algorithm, especially when the number of radio frequency links is greater than the number of data streams.

In mm-wave massive Multiple Input Multiple Output (MIMO) systems, in order to further improve the spectral efficiency of hybrid precoding in fully connected structure, an Alternate Minimization based on Gradient Descent (GD-AltMin) hybrid precoding algorithm is proposed. Firstly, the right singular vector of the channel matrix is used to initialize the analog precoding matrix. Secondly, digital and analog precoding matrices are updated by least square criterion and gradient descent method respectively. Then, under the principle of alternating minimization, the digital and analog precoding matrices are updated iteratively until the optimal digital and analog precoding matrices are obtained. Through theoretical analysis and numerical simulation, the spectral efficiency of several classical algorithms are compared under different signal-to-noise-ratio, number of radio frequency links and number of transmitting antennas. The results show that the spectral efficiency of the proposed algorithm is closer to the optimal unconstrained precoding algorithm than alternate minimization algorithm using phase extraction and channel singular value decomposition algorithm, especially when the number of radio frequency links is greater than the number of data streams.

In this paper we propose a solution strategy for the Cahn-Larché equations, which is a model for linearized elasticity in a medium with two elastic phases that evolve subject to a Ginzburg-Landau type energy functional. The system can be seen as a combination of the Cahn-Hilliard regularized interface equation and linearized elasticity, and is non-linearly coupled, has a fourth order term that comes from the Cahn-Hilliard subsystem, and is non-convex and nonlinear in both the phase-field and displacement variables. We propose a novel semi-implicit discretization in time that uses a standard convex-concave splitting method of the nonlinear double-well potential, as well as special treatment to the elastic energy. We show that the resulting discrete system is equivalent to a convex minimization problem, and propose and prove the convergence of alternating minimization applied to it. Finally, we present numerical experiments that show the robustness and effectiveness of both alternating minimization and the monolithic Newton method applied to the newly proposed discrete system of equations. We compare it to a system of equations that has been discretized with a standard convex-concave splitting of the double-well potential, and implicit evaluations of the elasticity contributions and show that the newly proposed discrete system is better conditioned for linearization techniques. [ABSTRACT FROM AUTHOR]

Archetypal analysis (AA) is an unsupervised learning method for exploratory data analysis. One major challenge that limits the applicability of AA in practice is the inherent computational complexity of the existing algorithms. In this paper, we provide a novel approximation approach to partially address this issue. Utilizing probabilistic ideas from high-dimensional geometry, we introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data, respectively. We prove that provided data are approximately embedded in a low-dimensional linear subspace and the convex hull of the corresponding representations is well approximated by a polytope with a few vertices, our method can effectively reduce the scaling of AA. Moreover, the solution of the reduced problem is near-optimal in terms of prediction errors. Our approach can be combined with other acceleration techniques to further mitigate the intrinsic complexity of AA. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets. [ABSTRACT FROM AUTHOR]

We pose the problem of the optimal approximation of a given nonnegative signal y t with the scalar autoconvolution (x ∗ x) t of a nonnegative signal x t , where x t and y t are signals of equal length. The I -divergence has been adopted as optimality criterion, being well suited to incorporate nonnegativity constraints. To find a minimizer we derive an iterative descent algorithm of the alternating minimization type. The algorithm is based on the lifting of the original problem to a larger space, a relaxation technique developed by Csiszár and Tusnády in [Statistics & Decisions (S1) (1984), 205–237] which, in the present context, requires the solution of a hard partial minimization problem. We study the asymptotic behavior of the algorithm exploiting the optimality properties of the partial minimization problems and prove, among other results, that its limit points are Kuhn–Tucker points of the original minimization problem. Numerical experiments illustrate the results. [ABSTRACT FROM AUTHOR]

We address the problem of federated learning (FL) where users are distributed and partitioned into clusters. This setup captures settings where different groups of users have their own objectives (learning tasks) but by aggregating their data with others in the same cluster (same learning task), they can leverage the strength in numbers in order to perform more efficient federated learning. For this new framework of clustered federated learning, we propose the Iterative Federated Clustering Algorithm (IFCA), which alternately estimates the cluster identities of the users and optimizes model parameters for the user clusters via gradient descent. We analyze the convergence rate of this algorithm first in a linear model with squared loss and then for generic strongly convex and smooth loss functions. We show that in both settings, with good initialization, IFCA is guaranteed to converge, and discuss the optimality of the statistical error rate. In particular, for the linear model with two clusters, we can guarantee that our algorithm converges as long as the initialization is slightly better than random. When the clustering structure is ambiguous, we propose to train the models by combining IFCA with the weight sharing technique in multi-task learning. In the experiments, we show that our algorithm can succeed even if we relax the requirements on initialization with random initialization and multiple restarts. We also present experimental results showing that our algorithm is efficient in non-convex problems such as neural networks. We demonstrate the benefits of IFCA over the baselines on several clustered FL benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm combining Bregman alternating minimization algorithm with two-step inertial force for solving a minimization problem composed of two nonsmooth functions with a smooth one in the absence of convexity. For solving nonconvex and nonsmooth problems, we give an abstract convergence theorem for general descent methods satisfying a sufficient decrease assumption, and allowing a relative error tolerance. Our result holds under the assumption that the objective function satisfies the Kurdyka–Łojasiewicz inequality. The proposed algorithm is shown to satisfy the requirements of our abstract convergence theorem. The convergence is obtained provided an appropriate regularization of the objective function satisfies the Kurdyka–Łojasiewicz inequality. Finally, numerical results are reported to show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Blind image deconvolution recovers a deblurred image and the blur kernel from a blurred image. From a mathematical point of view, this is a strongly ill-posed problem and several works have been proposed to address it. One successful approach proposed by Chan and Wong consists in using the total variation (TV) as a regularization for both the image and the kernel. These authors also introduced an Alternating Minimization (AM) algorithm in order to compute a physical solution. Unfortunately, Chan's approach suffers in particular from the ringing and staircasing effects produced by the TV regularization. To address these problems, we propose a new model based on Bilateral Total Variation (BTV) regularization of the image keeping the same regularization for the kernel. We prove the existence of a minimizer of a proposed variational problem in a suitable space using a relaxation process. We also propose an AM algorithm based on our model. The efficiency and robustness of our model are illustrated and compared with the TV method through numerical simulations. [ABSTRACT FROM AUTHOR]

The imaging quality of astronomical or space objects is significantly degraded by atmospheric turbulence, photon noise, image sensor noise, and other factors. A multi-channel alternating minimization (MCAM) method is proposed to restore degraded images, in which multiple blurred images at different times are selected, and the imaging object and the point spread function are reconstructed alternately. Results show that the restoration index can converge rapidly after two iterations of the MCAM method when six different images are adopted. According to the analysis of the structure similarity index, the stronger the influence of turbulence and mixed noise, the higher the degree of image improvement. The above results can provide a reference for blind restoration of images degraded by atmospheric turbulence and mixed noises. [ABSTRACT FROM AUTHOR]

The hybrid precoding problem in point-to-point millimeter wave (mmWave) multiple input multiple output (MIMO) for narrowband channel has been established as a Frobenius norm minimization problem. It is translated into trace minimization problem, and two algorithms are proposed to solve it. In the first method based on alternating minimization, we alternately determine the analog precoder and digital precoder, keeping the other constant to minimize the trace. The analog precoding subproblem with the fixed digital precoder is converted into a semi-definite programming (SDP) problem and solved by block coordinate descent (BCD) algorithm with suitable modifications. In the second method, we segregate the analog precoding and digital precoding subproblems by considering orthogonality of analog precoder. The analog precoding is further rephrased as a trace maximization problem and solved by an iterative power method by enforcing orthogonality constraint on the analog precoder. The adapted form of modified Gramm-Schmidt orthogonalization procedure is employed to impose orthogonality on the analog precoder. The proposed methods are extended for wideband channel by considering orthogonal frequency division multiplexing (OFDM). The proposed methods not only exhibit a good performance but also come with lower computational complexity when compared to existing methods with comparable performances.

Limited angle reconstruction is a typical ill-posed problem in computed tomography (CT). Given incomplete projection data, images reconstructed by conventional analytical algorithms and iterative methods suffer from severe structural distortions and artifacts. In this paper, we proposed a self-augmented multi-stage deep-learning network (Sam’s Net) for end-to-end reconstruction of limited angle CT. With the merit of the alternating minimization technique, Sam’s Net integrates multi-stage self-constraints into cross-domain optimization to provide additional constraints on the manifold of neural networks. In practice, a sinogram completion network (SCNet) and artifact suppression network (ASNet), together with domain transformation layers constitute the backbone for cross-domain optimization. An online self-augmentation module was designed following the manner defined by alternating minimization, which enables a self-augmented learning procedure and multi-stage inference manner. Besides, a substitution operation was applied as a hard constraint for the solution space based on the data fidelity and a learnable weighting layer was constructed for data consistency refinement. Sam’s Net forms a new framework for ill-posed reconstruction problems. In the training phase, the self-augmented procedure guides the optimization into a tightened solution space with enriched diverse data distribution and enhanced data consistency. In the inference phase, multi-stage prediction can improve performance progressively. Extensive experiments with both simulated and practical projections under 90-degree and 120-degree fan-beam configurations validate that Sam’s Net can significantly improve the reconstruction quality with high stability and robustness. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization arises widely in machine learning and data analysis. In this paper, for a given factorization of rank r, we consider the sparse stochastic matrix factorization (SSMF) of decomposing a prescribed m-by-n stochastic matrix V into a product of an m-by-r stochastic matrix W and an r-by-n stochastic matrix H, where both W and H are required to be sparse. With the prescribed sparsity level, we reformulate the SSMF as an unconstrained nonconvex-nonsmooth minimization problem and introduce a columnwise update algorithm for solving the minimization problem. We show that our algorithm converges globally. The main advantage of our algorithm is that the generated sequence converges to a special critical point of the cost function, which is nearly a global minimizer over each column vector of the W-factor and is a global minimizer over the H-factor as a whole if there is no sparsity requirement on H. Numerical experiments on both synthetic and real data sets are given to demonstrate the effectiveness of our proposed algorithm. [ABSTRACT FROM AUTHOR]

To improve the detection speed for wide-frequency dense signals (WFDSs), a fast minimization algorithm (FMA) was proposed in this study. Firstly, this study modeled the WFDSs and performed a Taylor-series expansion of the sampled model. Secondly, we simplified the sampling model based on the augmented Lagrange multiplier (ALM) method and then calculated the augmented Lagrange function of the sampling model. Finally, according to the alternating minimization strategy, the Lagrange multiplier vector and the sparse block phasor in the function were iterated individually to realize the measurement of the original signal components. The results show that the algorithm improved the analysis accuracy of the WFDS by 35% to 46% on the IEEE C37.118.1a-2014 standard for the wide-frequency noise test, harmonic modulation test, and step-change test, providing a theoretical basis for the development of the P-class phasor measurement unit (PMU). [ABSTRACT FROM AUTHOR]

In this paper, a new total generalized variational (TGV) model for restoring images with Cauchy noise is proposed, which contains a non-convex fidelity term and a TGV regularization term. In order to obtain a strictly convex model, we add an appropriate proximal term to the non-convex fidelity term. We prove that the solution of the proposed model exists and is unique. Due to the convexity of the proposed model and in order to get a convergent algorithm, we employ an alternating minimization algorithm to solve the proposed model. Finally, we demonstrate the performance of our scheme by numerical examples. Numerical results demonstrate that the proposed algorithm significantly outperforms some previous methods for Cauchy noise removal.

Low-rank tensor regression (LRTR) problems are widely studied in statistics and machine learning, in which the regressors are generally grouped by clustering strongly correlated variables or variables corresponding to different levels of the same predictive factor in many practical applications. By virtue of the idea of group selection in the classical linear regression framework, we propose an LRTR method for adaptive selection of grouped variables in this article, which is formulated as a group SLOPE penalized low-rank, orthogonally decomposable tensor optimization problem. Moreover, we introduce the notion of tensor group false discovery rate (TgFDR) to measure the group selection performance. The proposed regression method provably controls TgFDR and achieves the asymptotically minimax estimate under the assumption that variable groups are orthogonal to each other. Finally, an alternating minimization algorithm is developed for efficient problem resolution. We demonstrate the performance of our proposed method in group selection and low-rank estimation through simulation studies and real dataset analysis. [ABSTRACT FROM AUTHOR]

Low-rank tensor completion (LRTC) that aims to restore the latent clean data from an incomplete and/or degraded observation, shows promising results in ubiquitous tensorial data completion applications. Most tensor completion approaches are vulnerable to outliers since their derivations are based on $\ell _{2}$ -space to be robust against Gaussian noise. In this work, to tackle this issue, $\ell _{p}$ -regression $(0 < p < 2)$ is employed to achieve outlier resistance, where a factored form of tensor train (TT)-format representation is regularized by the low-TT-rank prior to exploit the inter-fibers correlation. On the basis of that, an effective iterative $\ell _{p}$ -regression TT completion method (referred to $\ell _{p}$ -TTC) is proposed, with the advantage of not requiring the hard-to-determine user-defined weights in TT rank model. Extensive experiment results are presented to demonstrate the outlier resistance of the proposed $\ell _{p}$ -TTC, and showing the effective and superior performance in both bistatic MIMO radar localization and color image inpainting and denoising, compared with state-of-the-art tensor completion approaches. [ABSTRACT FROM AUTHOR]

A variable-phase-shifter (VPS) architecture with hybrid precoding for mixture use of phase shifters and switches, is proposed for millimeter wave massive multiple-input multiple-output communications. For the VPS architecture, a hybrid precoding design (HPD) scheme, called VPS-HPD, is proposed to optimize the phases according to the channel state information by alternately optimizing the analog precoder and digital precoder. To reduce the computational complexity of the VPS-HPD scheme, a low-complexity HPD scheme for the VPS architecture (VPS-LC-HPD) including alternating optimization in three stages is then proposed, where each stage has a closed-form solution and can be efficiently implemented. To reduce the hardware complexity introduced by the large number of switches, we consider a group-connected VPS architecture and propose a HPD scheme, where the HPD problem is divided into multiple independent subproblems with each subproblem flexibly solved by the VPS-HPD or VPS-LC-HPD scheme. Simulation results verify the effectiveness of the propose schemes and show that the proposed schemes can achieve satisfactory spectral efficiency performance with reduced computational complexity or hardware complexity. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the precoder design for multiple-input multiple-output (MIMO) dual-functional radar-communication (DFRC) system with one-bit digital-to-analog converters (DACs). In order to form the dual-functional beam-pattern, we formulate the precoding problem as a weighted optimization problem with the constant modulus constraint, which aims at minimizing the average error power and guaranteeing radar waveform similarity. The problem is divided into three sub-problems corresponding to the multiple variables, i.e., the precoding factor, transmit signal matrix, and radar waveform matrix. Due to the discrete and non-convex properties of the optimization problem, we propose a multi-variable alternating minimization (MVAM) framework to achieve the near-optimal solutions. The precoding factor and radar waveform can be solved in closed-forms. For the transmit signal matrix, we devise a binary particle swarm optimization-simulated annealing (BPSO-SA) algorithm to obtain it under the MVAM framework. Extensive simulations validate the effectiveness of the proposed approach under various scenarios, including the case without perfect channel state information. The simulation results show that, compared with existing non-linear precoders, the proposed approach achieves 7dB SNR gain at the bit error rate of 10−4 in the 8-antenna system, and the gain of SNR is 0.2dB in the massive MIMO system with 128 antennas. [ABSTRACT FROM AUTHOR]

In recent years, even though Stochastic Gradient Descent (SGD) and its variants are well-known for training neural networks, it suffers from limitations such as the lack of theoretical guarantees, vanishing gradients, and excessive sensitivity to input. To overcome these drawbacks, alternating minimization methods have attracted fast-increasing attention recently. As an emerging and open domain, however, several new challenges need to be addressed, including 1) Convergence properties are sensitive to penalty parameters, and 2) Slow theoretical convergence rate. We, therefore, propose a novel monotonous Deep Learning Alternating Minimization (mDLAM) algorithm to deal with these two challenges. Our innovative inequality-constrained formulation infinitely approximates the original problem with non-convex equality constraints, enabling our convergence proof of the proposed mDLAM algorithm regardless of the choice of hyperparameters. Our mDLAM algorithm is shown to achieve a fast linear convergence by the Nesterov acceleration technique. Extensive experiments on multiple benchmark datasets demonstrate the convergence, effectiveness, and efficiency of the proposed mDLAM algorithm. [ABSTRACT FROM AUTHOR]