Search

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 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]

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]

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.

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]

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]

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]

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]

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]

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 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]

This study considers the constructive interference-based symbol-level precoding design problem in millimeter-wave massive multiuser multiple-input multiple-output systems with hybrid analog-and-digital precoding architecture. In contrast to traditional hybrid precoding architecture in which the analog part is implemented by infinite-resolution phase shifters, analog precoders are achieved in this study using low-cost and energy-efficient switches and inverters. Our objective is to design a hybrid precoder that minimizes the Euclidean distance between the hybrid precoder and the optimal fully digital precoder. However, such a design problem is difficult due to the intricate coupling of digital and analog precoder variables. Thus, we apply the alternating minimization (AltMin) framework to decouple the considered problem into digital and analog precoder design problems and then solve for digital and analog precoders in an alternating manner. By adopting the AltMin framework, we obtain a closed-form solution for digital precoder. Nevertheless, solving the analog precoder design problem incurs combinatorial complexity, which we address by proposing a coordinate descent algorithm to sequentially update each element of the analog precoder with a closed-form expression. Simulation results reveal that the application of the proposed algorithm for the proposed hardware-efficient hybrid precoding architecture provides the desired balance among symbol error rate performance, power consumption, and hardware cost.

Max-affine regression refers to a model where the unknown regression function is modeled as a maximum of $k$ unknown affine functions for a fixed $k \geq 1$. This generalizes linear regression and (real) phase retrieval, and is closely related to convex regression. We study this problem in the high-dimensional setting assuming that $k$ is a fixed constant, and focus on the estimation of the unknown coefficients of the affine functions underlying the model. We analyze a natural alternating minimization (AM) algorithm for the non-convex least squares objective when the design is Gaussian. We show that the AM algorithm, when initialized suitably, converges with high probability and at a geometric rate to a small ball around the optimal coefficients. In order to initialize the algorithm, we propose and analyze a combination of a spectral method and a search algorithm in a low-dimensional space, which may be of independent interest. The final rate that we obtain is near-parametric and minimax optimal (up to a polylogarithmic factor) as a function of the dimension, sample size, and noise variance. In that sense, our approach should be viewed as a direct and implementable method of enforcing regularization to alleviate the curse of dimensionality in problems of the convex regression type. Numerical experiments illustrate the sharpness of our bounds in the various problem parameters. [ABSTRACT FROM AUTHOR]

We consider the problem of sparse coding, where each sample consists of asparse linear combination of a set of dictionary atoms, and the task is tolearn both the dictionary elements and the mixing coefficients. Alternatingminimization is a popular heuristic for sparse coding, where the dictionary andthe coefficients are estimated in alternate steps, keeping the other fixed.Typically, the coefficients are estimated via $\ell_1$ minimization, keepingthe dictionary fixed, and the dictionary is estimated through least squares,keeping the coefficients fixed. In this paper, we establish local linearconvergence for this variant of alternating minimization and establish that thebasin of attraction for the global optimum (corresponding to the truedictionary and the coefficients) is $\order{1/s^2}$, where $s$ is the sparsitylevel in each sample and the dictionary satisfies RIP. Combined with the recentresults of approximate dictionary estimation, this yields provable guaranteesfor exact recovery of both the dictionary elements and the coefficients, whenthe dictionary elements are incoherent.

The paper considers a Mixture Multilayer Stochastic Block Model (MMLSBM), where layers can be partitioned into groups of similar networks, and networks in each group are equipped with a distinct Stochastic Block Model. The goal is to partition the multilayer network into clusters of similar layers, and to identify communities in those layers. Jing et al. (2020) introduced the MMLSBM and developed a clustering methodology, TWIST, based on regularized tensor decomposition. The present paper proposes a different technique, an alternating minimization algorithm (ALMA), that aims at simultaneous recovery of the layer partition, together with estimation of the matrices of connection probabilities of the distinct layers. Compared to TWIST, ALMA achieves higher accuracy both theoretically and numerically. [ABSTRACT FROM AUTHOR]

This paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. The objective of CluSL is to simultaneously find the best clusters of the data points and minimize the sum of loss functions within each cluster. This framework has many potential applications in healthcare, operations management, manufacturing, and so on. Because CluSL, in general, is nonconvex, we develop a regularized alternating minimization (RAM) algorithm to solve it, where at each iteration, we penalize the distance between the current clustering solution and the one from the previous iteration. By choosing a proper penalty function, we show that each iteration of the RAM algorithm can be computed efficiently. We further prove that the proposed RAM algorithm will always converge to a stationary point within a finite number of iterations. This is the first known convergence result in cluster-aware learning literature. Furthermore, we extend CluSL to the high-dimensional data sets, termed the F-CluSL framework. In F-CluSL, we cluster features and minimize loss function at the same time. Similarly, to solve F-CluSL, a variant of the RAM algorithm (i.e., F-RAM) is developed and proven to be convergent to an ∈ -stationary point. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can outperform the existing ones such as random forests and support vector classification, both in the interpretability of learning results and in prediction accuracy. Summary of Contribution: Aligned with the mission and scope of the INFORMS Journal on Computing, this paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. Because CluSL is, in general, nonconvex, a regularized alternating projection algorithm is developed to solve it and is proven to always find a stationary solution. We further generalize the framework to the high-dimensional data set, F-CluSL. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can deliver more interpretable learning results and outperform the existing ones such as random forests and support vector classification in computational time and prediction accuracy. [ABSTRACT FROM AUTHOR]

Multirobot simultaneous localization and mapping (SLAM) requires technical ingredients such as systematic construction of multiple SLAM systems and collection of information from each robot. In particular, map fusion is an essential process of multirobot SLAM that combines multiple local maps estimated by team robots into a global map. Fusion of multiple local maps is usually based on interloop detection that recognizes the same scene visited by multiple robots, or robot rendezvous where a member(s) of a robot team is observed in another member's images. This article proposes a collaborative monocular SLAM including a map fusion algorithm that utilizes rendezvous, which can happen when multirobot team members operate in close proximity. Unlike existing rendezvous-based approaches that require additional sensors, the proposed system uses a monocular camera only. Our system can recognize robot rendezvous using nonstatic features (NSFs) without fiducial markers to identify team robots. NSFs, which are abandoned as outliers in typical SLAM systems for not supporting ego-motion, can include relative bearing measurements between robots in a rendezvous situation. The proposed pipeline consists of the following: first, a feature identification module that extracts the relative bearing measurements between robots from NSFs consisting of anonymous bearing vectors with false positives, and second, a map fusion module that integrates the map from the observer robot with the maps from the observed robots using identified relative measurements. The feature identification module can operate quickly using the proposed alternating minimization algorithm formulated by two subproblems with closed-form solutions. The experimental results confirm that our collaborative monocular SLAM system recognizes rendezvous rapidly and robustly, and fuses local maps of team robots into a global map accurately. [ABSTRACT FROM AUTHOR]

Data-driven computing in elasticity attempts to directly use experimental data on material, without constructing an empirical model of the constitutive relation, to predict an equilibrium state of a structure subjected to a specified external load. Provided that a data set comprising stress–strain pairs of material is available, a data-driven method using the kernel method and the regularized least-squares was developed to extract a manifold on which the points in the data set approximately lie (Kanno 2021, Jpn. J. Ind. Appl. Math.). From the perspective of physical experiments, stress field cannot be directly measured, while displacement and force fields are measurable. In this study, we extend the previous kernel method to the situation that pairs of displacement and force, instead of pairs of stress and strain, are available as an input data set. A new regularized least-squares problem is formulated in this problem setting, and an alternating minimization algorithm is proposed to solve the problem.

Image nonlocal self-similarity (NSS) property has been widely exploited via various sparsity models such as joint sparsity (JS) and group sparse coding (GSC). However, the existing NSS-based sparsity models are either too restrictive, e.g., JS enforces the sparse codes to share the same support, or too general, e.g., GSC imposes only plain sparsity on the group coefficients, which limit their effectiveness for modeling real images. In this paper, we propose a novel NSS-based sparsity model, namely, low-rank regularized group sparse coding (LR-GSC), to bridge the gap between the popular GSC and JS. The proposed LR-GSC model simultaneously exploits the sparsity and low-rankness of the dictionary-domain coefficients for each group of similar patches. An alternating minimization with an adaptive adjusted parameter strategy is developed to solve the proposed optimization problem for different image restoration tasks, including image denoising, image deblocking, image inpainting, and image compressive sensing. Extensive experimental results demonstrate that the proposed LR-GSC algorithm outperforms many popular or state-of-the-art methods in terms of objective and perceptual metrics. [ABSTRACT FROM AUTHOR]

A single-index model is given by y = g*(< x, θ* >) + ε : The scalar response y depends on the covariate vector x both through an unknown (vector) parameter θ* as well as an unknown, non-parametric, univariate link-function g* ∈ G. We study the problem of recovering the parameter θ* from i.i.d. samples of the model when the covariates are drawn from a normal distribution. Our focus is on leveraging information about the (known) function class G in order to design a procedure that adapts to the noise level in the problem, thereby reducing the bias of parameter estimation. We show that when given access to a natural “labeling oracle”, our procedure recovers the underlying parameter at a rate that depends explicitly on how well we are able to estimate a suitably defined “inverse” link function. Both the procedure and its analysis framework are flexible, admitting any black-box estimator for the inverse link function. The resulting rate of parameter estimation significantly improves upon the risk of classical semi-parametric procedures whenever consistent estimates of the inverse link function can be obtained. When the function class G is appropriately structured and empirical risk minimization is used to estimate the inverse function, we provide quantitative upper bounds on the risk that depend on natural complexity measures of the class of inverse functions. We specialize our framework to the case where G is a sub-class of monotone single-index models, showing a computationally efficient, end-to-end algorithm that achieves very fast rates of parameter estimation in the regime in which the signal-to-noise ratio in the problem is large. We also pay particular attention to parameter identifiability in the noiseless model, deriving sharper upper bounds as well as information-theoretic lower bounds. Consequences for some unimodal SIMs and the (real) phase retrieval problem are also discussed. [ABSTRACT FROM AUTHOR]

This paper introduces the antenna selection (AS) mechanism into the quantized constant envelope (CE) precoding in massive multiuser multiple-input multiple-output systems to simultaneously reduce multiuser interference and hardware power consumption. However, this joint design problem requires optimizing over the precoding vector, the precoding factor, and the selected antenna subset. Unfortunately, these design parameters are connected. To address this problem, we propose an iterative algorithm developed from the alternating minimization (AltMin) framework to decouple the considered problem into two subproblems: the precoding factor design problem and the joint AS and the precoding vector design problem. The former can be easily solved approximately, whereas the latter incurs combinatorial complexity. We address this issue by using a simple yet effective coordinate update algorithm (CUA). We also develop a reduced-complexity version of CUA without performance loss. Moreover, the proposed CUA-based AltMin algorithm can be applied to the quantized CE precoding design problems without modification. The simulation results show that the proposed CUA-based AltMin algorithm considerably outperforms the existing algorithms for the quantized CE precoding design problems. In addition, when the AS mechanism is included in the quantized CE precoding design, CUA-AltMin with AS achieves the same or higher performance than CUA-AltMin without AS while providing further power savings.

Self-interference occurs when there is electromagnetic coupling between the transmission and reception of the same node; thus, degrading the RX sensitivity to incoming signals. In this paper we present a low-complexity technique for self-interference cancellation in multiple carrier multiple access systems employing whole band direct to digital sampling. In this scenario, multiple users are simultaneously received and transmitted by the system at overlapping arbitrary bandwidths and powers. Traditional algorithms for self-interference mitigation based on recursive least squares (RLS) or least mean squares (LMS), fail to provide sufficient rejection, since the incoming signal is far from being spectrally flat, which is critical for their performance. The proposed algorithm mitigates the interference by modeling the incoming multiple user signal as an autoregressive (AR) process and jointly estimates the AR parameters and self-interference. The resulting algorithm can be implemented using a low-complexity architecture comprised of only two RLS modules. The novel algorithm further satisfies low latency constraints and is adaptive, supporting time varying channel conditions. We compare this to many self-interference cancellation algorithms, mostly adopted from the acoustic echo cancellation literature, and show significant performance gain.

The $k$ -vectors algorithm for learning regression functions proposed here is akin to the well-known $k$ -means algorithm. Both algorithms partition the feature space, but unlike the $k$ -means algorithm, the $k$ -vectors algorithm aims to reconstruct the response rather than the feature. The partitioning rule of the algorithm is based on maximizing the correlation (inner product) of the feature vector with a set of $k$ vectors, and generates polyhedral cells, similar to the ones generated by the nearest-neighbor rule of the $k$ -means algorithm. Similarly to $k$ -means, the learning algorithm alternates between two types of steps. In the first type of steps, $k$ labels are determined via a centroid-type rule (in the response space), which uses a surrogate hinge-type loss function to the mean squared error loss function. In the second type of steps, the $k$ vectors which determine the partition are updated according to a multiclass classification rule, in the spirit of support vector machines. It is proved that both steps of the algorithm only require solving convex optimization problems, and that the algorithm is empirically consistent - as the length of the training sequence increases to infinity, fixed-points of the empirical version of the algorithm tend to fixed points of the population version of the algorithm. Learnability of the predictor class posit by the algorithm is also established. [ABSTRACT FROM AUTHOR]

This work analyzes the alternating minimization (AM) method for solving double sparsity constrained minimization problem, where the decision variable vector is split into two blocks. The objective function is a separable smooth function in terms of the two blocks. We analyze the convergence of the method for the non-convex objective function and prove a rate of convergence of the norms of the partial gradient mappings. Then, we establish a non-asymptotic sub-linear rate of convergence under the assumption of convexity and the Lipschitz continuity of the gradient of the objective function. To solve the sub-problems of the AM method, we adopt the so-called iterative thresholding method and study their analytical properties. Finally, some future works are discussed. [ABSTRACT FROM AUTHOR]

This paper considers the problem of phase retrieval, where the goal is to recover a signal z ∈ C n from the observations y i = | a i ⁎ z | , i = 1 , 2 , ⋯ , m. While many algorithms have been proposed, the alternating minimization algorithm is still one of the most commonly used and the simplest methods. Existing works have proved that when the observation vectors { a i } i = 1 m are sampled from a complex normal distribution C N (0 , I) , the alternating minimization algorithm recovers the underlying signal with a good initialization when m = O (n) , or with random initialization when m = O (n 2) , and it is conjectured that random initialization succeeds with m = O (n) [26]. This work proposes a modified alternating minimization method in a batch setting and proves that when m = O (n log 5 ⁡ n) , the proposed algorithm with random initialization recovers the underlying signal with high probability. The proof is based on the observation that after each iteration of alternating minimization, with high probability, the correlation between the direction of the estimated signal and the direction of the underlying signal increases. [ABSTRACT FROM AUTHOR]

Regularization-based image restoration is one of the most powerful tools in image processing and computer vision thanks to its flexibility for handling various inverse problems. However, designing an optimal regularization function still remains unsolved since natural images and related scene types have a complex structure. In this paper, we present a general and principled framework, called deeply aggregated alternating minimization (DeepAM). We design a convolutional neural network (CNN) to implicitly parameterize the regularizer of the alternating minimization (AM) algorithm. Contrary to the conventional AM algorithm based on a point-wise proximal mapping, the DeepAM projects intermediate estimate into a set of natural images via deep aggregation. Since the CNN is fully integrated into the AM procedure, all parameters can be jointly optimized through end-to-end training. These properties enable the DeepAM to converge with a small number of iterations, while maintaining an algorithmic simplicity. We show that the DeepAM outperforms state-of-the-art methods, including nonlocal-based methods, Plug-and-Play regularization, and recent data-driven approaches. The effectiveness of our framework is demonstrated in a variety of image restoration tasks: Guassian denoising, deraining, deblurring, super-resolution, color-guided depth upsampling, and RGB/NIR restoration. [ABSTRACT FROM AUTHOR]

This study proposes two low-cost precoding architectures for massive multiuser multiple-input multiple-output systems to alleviate multiuser interference, where one has the objective of reducing the power consumption of the conventional 1-bit precoding architecture and the another has the objective of improving the performance of the conventional 1-bit precoding schemes. However, jointly identifying the precoding factor and the precoding vector of the proposed precoding architectures is intractable because they are coupled together. We address this issue by utilizing an alternating minimization (AltMin) framework to optimize alternatively the precoding factor and the precoding vector. Nevertheless, this framework experiences difficulty in optimizing the precoding vector, which we address by proposing a machine learning–inspired algorithm developed from the cross-entropy optimization (CEO) framework to obtain a near-optimal precoding vector. Although the CEO-based AltMin algorithm provides excellent performance, the complexity of the CEO part is relatively high. We thus develop an AltMin algorithm using a sequential greedy descent algorithm as a low-complexity counterpart of the CEO-based AltMin algorithm. Simulation results reveal that the proposed precoding algorithms can successfully determine the weights of the proposed precoding architectures, thereby providing considerable performance improvements over previous 1-bit precoding algorithms. Moreover, the hardware complexity and power consumption of the proposed precoding architectures are considerably lower than those of previous 1-bit precoding architectures. [ABSTRACT FROM AUTHOR]

Data completion is a problem of filling missing or unobserved elements of partially observed datasets. Data completion algorithms have received wide attention and achievements in diverse domains including data mining, signal processing, and computer vision. We observe a ubiquitous tubal-sampling pattern in big data and Internet of Things (IoT) applications, which is introduced by many reasons such as high data acquisition cost, downsampling for data compression, sensor node failures, and packet losses in low-power wireless transmissions. To meet the time and accuracy requirements of applications, data completion methods are expected to be accurate as well as fast. However, the existing methods for data completion with the tubal-sampling pattern are either accurate or fast, but not both. In this article, we propose high-performance graphics processing unit (GPU) tensor completion for data completion with the tubal-sampling pattern. First, by exploiting the convolution theorem, we split a tensor least-squares minimization problem into multiple least-squares sub-problems in the frequency domain. In this way, massive parallelisms are exposed for many-core GPU architectures while still preserving high recovery accuracy. Second, we propose computing slice-level and tube-level tasks in batches to improve GPU utilization. Third, we reduce the data transfer cost by eliminating the accesses to the CPU memory inside algorithm loop structures. The experimental results show that the proposed tensor completion is both fast and accurate. Using synthetic data of varying sizes, the proposed GPU tensor completion achieves maximum $248.18 \times$ 248. 18 × , $7,403.27 \times$ 7 , 403. 27 × , and $33.27 \times$ 33. 27 × speedups over the CPU MATLAB implementation, GPU element-sampling tensor completion in the cuTensor-tubal library, and GPU high-performance matrix completion, respectively. With a 50 percent sampling rate, the proposed GPU tensor completion achieves a recovery error of $1.40e$ 1. 40 e -5, which is comparable with that of the GPU element-sampling tensor completion and three orders of magnitude better than that of the GPU high-performance matrix completion. To utilize multiple GPUs in servers, we design a multi-GPU scheme for tubal-sampling tensor completion. The multi-GPU tensor completion achieves maximum $1.89 \times$ 1. 89 × speedup on two GPUs versus on a single GPU for medium or big tensors. We further evaluate the performance of the proposed GPU tensor completion in three real applications, namely, video transmission in wireless camera networks, RF fingerprint-based indoor localization, and seismic data completion, and it achieves maximum speedups of $448.68 \times$ 448. 68 × , $24.63 \times$ 24. 63 × , and $311.54 \times$ 311. 54 × , respectively. We integrate this high-performance GPU tensor completion implementation into the cuTensor-tubal library to support various applications. [ABSTRACT FROM AUTHOR]

• Consider piecewise constant of the reflectance. • Introduce the total variation term in the proposed model. • Establish the existence of the minimizers to the proposed model. • Design an alternating minimization algorithm to solve the proposed model. Image segmentation methods usually suffer from intensity inhomogeneity problem caused by many factors such as spatial variations in illumination (or bias fields of imaging devices). In order to address this problem, this paper proposes a Retinex-based variational model for image segmentation and bias correction. According to Retinex theory, the input inhomogeneous image can be decoupled into illumination bias and reflectance parts. The main contribution of this paper is to consider piecewise constant of the reflectance, and thereby introduce the total variation term in the proposed model for correcting and segmenting the input image. This is different from the existing model in which the spatial smoothness of the illumination bias is employed only. The existence of the minimizers to the variational model is established. Furthermore, we develop an efficient algorithm to solve the model numerically by using the alternating minimization method. Our experimental results are reported to demonstrate the effectiveness of the proposed method, and its performance is competitive with that of the other testing methods. [ABSTRACT FROM AUTHOR]

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called Tubal-AltMin, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-AltMin alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Secondly, the theoretical performance guarantee is challenging since Tubal-AltMin is iterative and nonconvex. We prove that 1) Tubal-AltMin generates a best rank- $r$ approximate up to any predefined accuracy $\epsilon $ at an exponential rate, and 2) for an $n \times n \times k$ tensor $\mathcal {M}$ with tubal-rank $r \ll n$ , the required sampling complexity is $O((nr^{2}k ||\mathcal {M}||_{F}^{2} \log ^{3}~n) / \overline {\sigma }_{rk}^{2})$ , where $\overline {\sigma }_{rk}$ is the $rk$ -th singular value of the block diagonal matrix representation of $\mathcal {M}$ in the frequency domain, and the computational complexity is $O(n^{2}r^{2}k^{3} \log n \log (n/\epsilon))$. Finally, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization using alternating direction method of multipliers (TNN-ADMM), Tubal-AltMin-Simple (a simplified implementation of Tubal-AltMin) improves the recovery error by several orders of magnitude. In experiments, Tubal-AltMin-Simple is faster than TNN-ADMM by a factor of 5 for a $200 \times 200 \times 20$ tensor. [ABSTRACT FROM AUTHOR]

When wireless transmission is performed over the bandwidth in the order of a gigahertz, high-resolution analog-to-digital converters (ADCs), and the large number of radio frequency chains significantly increase the power consumption. To address this issue, one promising technique is to use low-resolution, even one-bit ADCs. Another promising technique is to apply a hybrid precoding architecture to reduce the number of RF chains. In this paper, we propose to combine those techniques to reduce the hardware costs in multi-input multi-output system. Our objective is to optimize the hybrid precoder with the aim of increasing the achievable rate. To this end, we first derive an expression for the achievable rate in flat fading channels based on the Bussgang theorem, which is able to reformulate the nonlinear quantitative process as a linear function with identical firstand second-order statistics. To solve the non-convex hybrid precoding design problem, we treat the hybrid precoding design as a matrix factorization problem, which can be solved with an efficient alternating minimization algorithm. That is, we solve the digital precoder and the analog precoder in an alternative way in two separate subproblems. To find the optimal precoder in the first subproblem, we first prove the optimal structure of the digital precoding matrix. With it, we transfer the digital precoding design to a power allocation problem, the closed-form solution of which is then optimally found by using Karush-Kuhn-Tucker conditions. In the second subproblem, due to the non-convex modulusnorm constraint, it is challenging to directly solve the analog precoder. To resolve this problem, we propose to optimize the phases in the analog precoding matrix and adopt the subgradient algorithm to find the local optimal solution. Our simulation results show that the proposed hybrid precoding design effectively improves the achievable rates.

Improving the quality of reconstructed images in blind image restoration tasks remains a challenging and important problem. To solve this problem, a new methodology is proposed based on sparse representation and regularization. In this method, blind image restoration is divided into two steps: blur estimation and high-quality image reconstruction. In the blur estimation step, a new sparse regularized blur estimation model is built; it uses the l1 norm of the gradient image and the l1 - l2 mixed norm of the blur kernel as the regularization terms. The variable splitting method is applied to the sparse regularized blur estimation model to perform an equivalent model transformation; alternating minimization is then utilized to decompose the equivalent model into several simpler subproblems. As a result, the blur kernel estimate can be obtained with an alternating estimation approach for the subproblems by using a fast Fourier transform, soft-thresholding iteration, etc. To improve the accuracy, a multiscale strategy is integrated into the iterative estimation process of the blur kernel, and the model parameters are updated with a continuous method. In the clear image reconstruction stage, the image deconvolution problem in reconstruction is solved with a hyper-Laplacian sparse priorbased method. In the experiments, simulations are performed, and the results are compared with the results of two similar methods. In the experiment, famous synthetic blurred images and real-world blurred images from a public image library are used. The comparative results validate the effectiveness of the proposed method and demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

Natural image priors play an important role in image denoising, and various prior-based methods have been widely proposed for noise removal. However, these methods tend to smooth the fine image textures while suppressing noise, degrading the image visual quality. To address this problem, in this paper, we propose an adaptive texture-preserving denoising method. In contrast to most existing prior-based denoising methods, two types of priors [gradient histogram matching priors and nonlocal self-similarity (NSS) priors] are proposed, and their combination is used for image denoising. We introduce a hyper-Laplacian distribution of the gradient histogram matching prior, which enforces the gradient histogram of the denoised image to be as close as possible to the estimated reference histogram from the original image. Meanwhile, the proposed model obtained by introducing the NSS priors effectively preserves fine image details and generates sharp image edges. To improve the accuracy of the method, a content-adaptive parameter selection scheme based on edge detection filters is proposed. Moreover, the optimization problem with two types of priors and the content-adaptive parameter added into the objective function becomes a challenging non-convex optimization problem. To effectively solve this problem, we have developed a new numerical solution based on augmented Lagrangian multipliers and alternating minimization scheme. The experimental results demonstrate that the proposed method effectively preserves the texture features of the denoised images and outperforms several variational methods and other state-of-the-art methods in terms of various evaluation indices and visual quality, especially at medium and high noise levels. [ABSTRACT FROM AUTHOR]