publications

Theses

2024

1. PhD Thesis

   

   A parallel successive convex approximation framework with smoothing majorization for phase retrieval

   Tianyi Liu

   Technische Universität Darmstadt, Oct 2024

   Abs DOI Slides

   This dissertation is concerned with the design and analysis of approximation-based methods for nonconvex nonsmooth optimization problems. The main idea behind those methods is to solve a difficult optimization problem by converting it into a sequence of simpler surrogate/approximate problems. In the two widely-used optimization frameworks, namely, the majorization-minimization (MM) framework and the successive convex approximation (SCA) framework, the approximate function is designed to be a global upper bound, called majorizer, of the original objective function and convex, respectively. Generally speaking, there are two desiderata of the approximate function, i.e., the tightness to the original objective function and the low computational complexity of minimizing the approximate function. In particular, we focus on techniques that can be used to construct a parallelizable approximate problem so as to take advantage of modern multicore computing platforms. The first part of this thesis aims to develop an efficient parallelizable algorithmic framework based on approximation techniques for a broad class of nonconvex nonsmooth optimization problems. The classic convergence result of MM is established on the consistency of directional derivatives in all directions between the original objective function and its majorizer at the point where the majorizer is constructed. This requirement restricts the majorizer constructed at a nondifferentiable point of the original function to be also nonsmooth, which hinders its capability of simplifying nonsmooth problems since the minimization of the majorizing function, if restricted to be nonsmooth, may still be difficult. Therefore, in this thesis, we relax the derivative consistency in the majorization step so that a smooth majorizer that can be easily minimized is permitted for a wide class of nonsmooth problems. As a result of this relaxation of derivative consistency, the smoothing majorization leads to the convergence to a stationary solution in a more relaxed sense than the classic MM. Furthermore, in contrast to minimizing the possibly nonconvex majorizing function exactly, the smoothness of the majorizing function allows us to employ the idea of SCA, along with available separable approximation techniques, to obtain an approximate minimizer of the majorizing function efficiently. Thus, we develop a parallelizable inexact MM framework, termed smoothing SCA, by combining the smoothing majorization technique and the idea of successive convex approximation. In this framework, the construction of the approximate problem at each iteration is divided into two steps, namely, the smoothing majorization and the convex approximation, so that the two desiderata of the approximate function can be treated separately. In addition, both the exact and inexact MM with smoothing majorization can be implemented block-coordinatewise to exploit potential separable structures of the constraints in the optimization problem. The convergence behaviors of the proposed frameworks are analyzed accordingly. In the second part of this thesis, as our mainly promoted framework, the smoothing SCA framework is employed to address the phase retrieval with dictionary learning problem. Two efficient parallel algorithms are developed by applying the smoothing SCA to two complementary nonconvex nonsmooth formulations, respectively, which are both based on a least-squares criterion. The computational complexities of the proposed algorithms are theoretically analyzed and both their error performance and computational time are evaluated by extensive simulations in the context of blind channel estimation from subband magnitude measurements in multi-antenna random access network, in comparison to the state-of-the-art methods.

2018

1. Master Thesis

   A scalable graph-based mixed-integer linear programming approach for the examination timetabling problem

   Tianyi Liu

   Politecnico di Torino, Jul 2018

   Abs

   In this thesis the Examination Timetabling Problem (ETP) in the Darmstadt University of Technology (TU Darmstadt) is presented and a Mixed-Integer Linear Programming (MILP) model is proposed for it. Our model concentrates on the conflicts of students. An exam-based conflict graph in which edges represent incompatibilities between exams is used. An exact MILP approach is directly using a MIP solver to solve the model, which is usually not able to solve real instances due to the complexity. In order to achieve high-quality solutions within a short computational time, we propose a scalable approach based on decomposing the entire problem into subproblems, which can be easily handled using the exact MILP approach. This approach concentrates on dealing with the conflicts. The decomposition of the problem then corresponds to the decomposition of the conflict graph. For the test instances in this thesis, the scalable approach considerably improves the solutions even in shorter time, compared with the exact MILP approach.

Book Chapters

2022

1. Recovery under side constraints

   Khaled Ardah, Martin Haardt, Tianyi Liu, and 3 more authors

   In Compressed sensing in information processing, 2022

   Abs

   This chapter addresses sparse signal reconstruction under various types of structural side constraints with applications in multi-antenna systems. Side constraints may result from prior information on the measurement system and the sparse signal structure. They may involve the structure of the sensing matrix, the structure of the non-zero support values, the temporal structure of the sparse representation vector, and the nonlinear measurement structure. First, we demonstrate how a priori information in the form of structural side constraints influence recovery guarantees (null space properties) using \ell1-minimization. Furthermore, for constant modulus signals, signals with row, block, and rank sparsity, as well as non-circular signals, we illustrate how structural prior information can be used to devise efficient algorithms with improved recovery performance and reduced computational complexity. Finally, we address the measurement system design for linear and nonlinear measurements of sparse signals. To this end, we derive a new linear mixing matrix design based on coherence minimization. Then, we extend our focus to nonlinear measurement systems where we design parallel optimization algorithms to efficiently compute stationary points in the sparse phase-retrieval problem with and without dictionary learning.

Preprints

2024

1. arXiv

   Gridless parameter estimation in partly calibrated rectangular arrays

   Tianyi Liu, Sai Pavan Deram, Khaled Ardah, and 3 more authors

   Jun 2024

   Abs DOI

   Spatial frequency estimation from a mixture of noisy sinusoids finds applications in various fields. While subspace-based methods offer cost-effective super-resolution parameter estimation, they demand precise array calibration, posing challenges for large antennas. In contrast, sparsity-based approaches outperform subspace methods, especially in scenarios with limited snapshots or correlated sources. This study focuses on direction-of-arrival (DOA) estimation using a partly calibrated rectangular array with fully calibrated subarrays. A gridless sparse formulation leveraging shift invariances in the array is developed, yielding two competitive algorithms under the alternating direction method of multipliers (ADMM) and successive convex approximation frameworks, respectively. Numerical simulations show the superior error performance of our proposed method, particularly in highly correlated scenarios, compared to the conventional subspace-based methods. It is demonstrated that the proposed formulation can also be adopted in the fully calibrated case to improve the robustness of the subspace-based methods to the source correlation. Furthermore, we provide a generalization of the proposed method to a more challenging case where a part of the sensors is unobservable due to failures.

2. arXiv

   Maximum a posteriori direction-of-arrival estimation via mixed-integer semidefinite programming

   Tianyi Liu, Frederic Matter, Alexander Sorg, and 3 more authors

   Oct 2024

   Abs DOI

   In this paper, we consider the maximum a posteriori (MAP) estimation for the multiple measurement vectors (MMV) problem with application to direction-of-arrival (DOA) estimation, which is classically formulated as a regularized least-squares (LS) problem with an \ell_2,0-norm constraint, and derive an equivalent mixed-integer semidefinite program (MISDP) reformulation. The proposed MISDP reformulation can be exactly solved by a generic MISDP solver using a semidefinite programming (SDP) based branch-and-bound method, which, unlike other nonconvex approaches for the MMV problem, such as the greedy methods and sparse Bayesian learning techniques, provides a solution with an optimality assessment even with early termination. We also present an approximate solution approach based on randomized rounding that yields high-quality feasible solutions of the proposed MISDP reformulation at a practically affordable computation time for problems of extremely large dimensions. Numerical simulations demonstrate the improved error performance of our proposed method in comparison to several popular DOA estimation methods. In particular, compared to the deterministic maximum likelihood (DML) estimator, which is often used as a benchmark, the proposed method applied with the randomized rounding algorithm exhibits a superior estimation performance at a significantly reduced running time.

Journal Articles

2024

1. SP

   A tensor model for the calibration of air-coupled ultrasonic sensor arrays in 3D imaging

   Raphael Müller, Gianni Allevato, Matthias Rutsch, and 4 more authors

   Signal Processing, Nov 2024

   Abs DOI

   Arrays of ultrasonic sensors are capable of 3D imaging in air and an affordable supplement to other sensing modalities, such as radar, lidar, and camera, i.e.in heterogeneous sensing systems. However, manufacturing tolerances of air-coupled ultrasonic sensors may lead to amplitude and phase deviations. Together with artifacts from imperfect knowledge of the array geometry, there are numerous factors that can impair the imaging performance of an array. We propose a reference-based calibration method to overcome possible limitations. First, we introduce a novel tensor signal model to capture the characteristics of piezoelectric ultrasonic transducers (PUTs) and the underlying multidimensional nature of a multiple-input multiple-output (MIMO) sensor array. Second, we formulate and solve an optimization problem based on this model to obtain the calibrated parameters of the array. Third, we assess both our model and the commonly used analytic model using real data from a 3D imaging experiment. The experiment reveals that our array response model we learned with calibration data yields an imaging performance similar to that of the analytic array model, which requires perfect array geometry information.

2022

1. IEEE TSP

   

   Extended successive convex approximation for phase retrieval with dictionary learning

   Tianyi Liu, Andreas M. Tillmann, Yang Yang, and 2 more authors

   IEEE Transactions on Signal Processing, 2022

   Abs DOI PDF Poster

   Phase retrieval aims at recovering unknown signals from magnitude measurements of linear mixtures. In this paper, we consider the phase retrieval with dictionary learning problem, which includes another prior information that the signal admits a sparse representation over an unknown dictionary. The task is to jointly estimate the dictionary and the sparse representation from magnitude-only measurements. To this end, we study two complementary formulations and develop efficient parallel algorithms by extending the successive convex approximation framework using a smooth majorization. The first algorithm is termed compact-SCAphase and is preferable in the case of moderately diverse mixture models with a low number of mixing components. It adopts a compact formulation that avoids auxiliary variables. The proposed algorithm is highly scalable and has reduced parameter tuning cost. The second algorithm, referred to as SCAphase, uses auxiliary variables and is favorable in the case of highly diverse mixture models. It also renders simple incorporation of additional side constraints. The performance of both methods is evaluated when applied to blind channel estimation from subband magnitude measurements in a multi-antenna random access network. Simulation results show the efficiency of the proposed techniques compared to state-of-the-art methods.

Conference Proceedings

2024

1. IEEE SAM

   Blind phase-offset estimation in sparse partly calibrated arrays

   Tianyi Liu and Marius Pesavento

   In 2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM), Jul 2024

   Abs DOI Poster

   Spatial frequency estimation from a superposition of impinging waveforms in the presence of noise is important in many applications. While subspace-based methods offer high-resolution parameter estimation at a low computational cost, they heavily rely on precise array calibration with a synchronized clock, posing challenges for large distributed antenna arrays. In this study, we focus on direction-of-arrival (DoA) estimation within sparse partly calibrated rectangular arrays. These arrays consist of multiple perfectly calibrated sub arrays with unknown phase-offsets among them. We present a gridless sparse formulation for DoA estimation leveraging the multiple shift-invariance properties in the partly calibrated array. Additionally, an efficient blind calibration technique is proposed based on semidefinite relaxation to estimate the intersubarray phase-offsets accurately.

2. IEEE ICASSP

   Gridless parameter estimation in partly calibrated rectangular arrays

   Tianyi Liu, Sai Pavan Deram, Khaled Ardah, and 3 more authors

   In ICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Apr 2024

   Abs DOI Poster

   Spatial frequency estimation from a mixture of noisy sinusoids finds applications in various fields. The widely used subspace-based methods provide super-resolution parameter estimation at a low computational cost. However, they require an accurate array calibration, which is difficult for large antenna arrays. Sparsity-based methods have been shown to be more robust than subspace-based methods in difficult scenarios, e.g., in the case with a small number of snapshots and/or correlated sources. In this paper, we consider the direction-of-arrival (DOA) estimation in partly calibrated rectangular arrays comprising several calibrated and identical subarrays. We derive a gridless sparse formulation for DOA estimation based on the shift-invariance properties of the array and develop an efficient algorithm in the alternating direction method of multipliers (ADMM) framework. Numerical simulations show the superior error performance of our proposed method compared to subspace-based methods.

2023

1. IEEE CAMSAP

   Joint sparse estimation with cardinality constraint via mixed-integer semidefinite programming

   Tianyi Liu, Frederic Matter, Alexander Sorg, and 3 more authors

   In 2023 IEEE 9th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Dec 2023

   Abs DOI

   The multiple measurement vectors (MMV) problem refers to the joint estimation of multiple signal realizations where the signal samples share a common sparse support over a known dictionary, which is a fundamental challenge in various applications in signal processing, e.g., direction-of-arrival (DOA) estimation. We consider the maximum a posteriori (MAP) estimation of an MMV problem, which is classically formulated as a regularized least-squares (LS) problem with an \ell\textsubscript2,0-norm constraint and derive an equivalent mixed-integer semidefinite program (MISDP) reformulation, which can be solved by state-of-the-art numerical MISDP solvers at an affordable computation time. Numerical simulations in the context of DOA estimation demonstrate the improved error performance of our proposed method in comparison to several popular DOA estimation methods.

2. EUSIPCO

   Direction-of-arrival estimation for correlated sources and low sample size

   Yani Zhang, Tianyi Liu, and Marius Pesavento

   In 2023 31st European Signal Processing Conference (EUSIPCO), Sep 2023

   Abs DOI

   In this paper, we study the problem of recovering the direction-of-arrival in difficult scenarios of highly correlated source signals and only few available snapshots. Recently, the partial relaxation framework has been proposed as an optimizationbased technique that accounts for the existence of multiple signals while performing the estimation task through a simple spectral search. Its performance is superior to conventional methods but tends to deteriorate drastically when the source signals are highly correlated due to information loss associated with the relaxation. On the other hand, from a compressed sensing point of view, the recently proposed sparse row-norm reconstruction method formulates the parameter estimation problem as a compact \ell_2,1-mixed-norm minimization problem. One of its prominent advantages is its robustness under highly correlated sources and a low number of snapshots; an intrinsic bias induced by the \ell_1-norm approximation, however, affects the estimation performance. In this paper, we propose a method that integrates the \ell_2,1-mixed-norm minimization formulation into the spectral search of the partial relaxation estimators. Simulation results show that the proposed estimator has superior error performance in difficult scenarios and alleviates the disadvantages of both methods.

2021

1. IEEE ICASSP

   A parallel algorithm for phase retrieval with dictionary learning

   Tianyi Liu, Andreas M. Tillmann, Yang Yang, and 2 more authors

   In IEEE International Conference on Acoustics, Speech and Signal Processing, Jun 2021

   Abs DOI Poster

   We propose a new formulation for the joint phase retrieval and dictionary learning problem with a reduced number of regularization parameters to be tuned. A parallel algorithm based on the block successive convex approximation framework is developed for the proposed formulation. The performance of the algorithm is evaluated when applied to sparse channel estimation in a multi-antenna random access network. Simulation results on synthetic data show the efficiency of the proposed technique compared to the state-of-the-art method.

2020

1. IEEE SAM

   GPU-accelerated parallel optimization for sparse regularization

   Xingran Wang, Tianyi Liu, Minh Trinh-Hoang, and 1 more author

   In 2020 IEEE 11th Sensor Array and Multichannel Signal Processing Workshop (SAM), Jun 2020

   Abs DOI

   We prove the concept that the block successive convex approximation algorithm can be configured in a flexible manner to adjust for implementations on modern parallel hardware architecture. A shuffle order update scheme and an all-close termination criterion are considered for efficient performance and convergence comparisons. Four different implementations are studied and compared. Simulation results on hardware show the condition of using shuffle order and selection of block numbers and implementations.

2019

1. IEEE CAMSAP

   A block coordinate descent algorithm for sparse Gaussian graphical model inference with laplacian constraints

   Tianyi Liu, Minh Trinh-Hoang, Yang Yang, and 1 more author

   In IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Dec 2019

   Abs DOI

   We consider the problem of inferring sparse Gaussian graphical models with Laplacian constraints, which can also be viewed as learning a graph Laplacian such that the observed graph signals are smooth with respect to it. A block coordinate descent algorithm is proposed for the resulting linearly constrained log-determinant maximum likelihood estimation problem with sparse regularization. Simulation results on synthetic data show the efficiency of our proposed algorithm.

2. EUSIPCO

   A parallel optimization approach on the infinity norm minimization problem

   Tianyi Liu, Minh Trinh-Hoang, Yang Yang, and 1 more author

   In 2019 27th European Signal Processing Conference (EUSIPCO), Sep 2019

   DOI