Foundation and Reweighted Algorithms for Sparsest Points of Convex Sets with Application to Data Processing

Lead Research Organisation: University of Birmingham
Department Name: School of Mathematics

Abstract

Over the past a few years, the mathematical model for seeking sparsest solutions/points in a well-structured convex set has had a significant impact across disciplines. It becomes so important that seeking the sparsity has become a common request and task in such fields as signal recovery and denoising, image reconstruction and inpainting, face recognition, statistical estimation, pattern identification, model selection, machine learning, financial engineering, to name but a few. This, however, remains an emerging new area awaiting for urgent and extensive scientific research inputs. The proposed project aims to make significant UK contributions in this field, via providing sophisticated computational methods and related theory. The outcome of this proposed research will directly benefit to both academic and engineering communities. Up to now, the NP-hard sparsity-seeking model has been investigated dominantly by convex approximation method, i.e., l1-method. While it successfully solves a wide range of sparsity-seeking problems, it might fail in many situations as well. Reweighted methods have been numerically demonstrated being able to outperform the l1-method in many situations. However, the theoretical analysis for the reweighted algorithm is very limited so far, and many fundamental questions associated this method remain open. It is therefore imperative to develop a rigorous theory and efficient design for reweighted algorithms that, at present, lie at the research frontier of both applied mathematics and engineering. In this project, we aim at conducting a comprehensive and systematic study of such a theory and design, and to fully or partially address some important (open) questions in this field, and to apply the developed theory and algorithms timely to data processing, especially those from signal and image processing and financial problems. With a multidisciplinary character, the proposed research involves substantial exchange of ideas between applied mathematics (computational optimization and numerical analysis), engineering (sparse data representation and processing), and computer science (algorithmic design and complexity). We aim to achieve four closely related objectives. Successful completion one of these goals will bring useful ideas to achieve the next. First, we aim to enhance the existing theory and methods by developing new and relaxed conditions that guarantee the success of both weighted and non-weighted methods for locating sparsest points in convex sets. Second, we aim at developing a generic algorithmic framework and convergence theory for the general model of sparsity-seeking problems, leading to a new frontier in computational optimization, and stimulating more potential, complex applications in industrial sectors. Computer programs for research purpose (and possibly for commercial purpose later) will be compiled as well. Our third objective is largely to benefit academic communities by deeply exploring and deterministically justifying the interplay between reweighted and non-weighted algorithms. So far, this important research has not carried out yet in this field. Moreover, we aim for the deep relationship between the efficiency of reweighted algorithms and the concave minimization problem, leading to a new research frontier between the global optimization, fast data processing, and computational complexity.

Planned Impact

The development of efficient mathematical methods and related theory for a central problem lying at the research frontier of science and engineering will always have direct and indirect social and economic impacts.
The mathematical model in this proposed project, i.e., locating sparsest points in convex sets, is an emerging new topic that lies at the frontier of applied mathematics, engineering, information science and financial industry. Developing efficient computational methods and theory for this model is urgently needed in these fields. This is motivated and stimulated by the newly emerged compressive sensing theory that is initiating a new revolution in information science.
The applicant is convinced that the successful completion of the proposed research will have important and broad impacts on system engineering (especially in signal and image processing) and financial sectors, and in general on many end users sectors which are engaged in data processing and applications in such fields as science, control, planning, and information technologies. The results out of this project therefore will contribute to maintain and increase not only the UK's academic position in these fields, but more importantly, UK's industrial position in information technology, digital industry and medical image processing technology. The computational methods together with software developed in this project will directly help reduce the time and costs in various data processing (e.g. storage, compression, transmission, separation, and so on). This will broadly advance the design of products such as digital camera, medical scanning machine, and signal transmitter and receivers, and therefore improve the processing speed and quality of product, directly impacting on manufacturing and wealth creation as well.
Moreover, it is expected that the success of the research project will have direct or indirectly impact on any other areas that rely on this optimization model. For instance, policemen may use the face image identification and reconstruction to find the criminal, astrophysists deal with synchrotron emission images, and financial investors make their decisions under selection constraints. All these sectors require a fast, stable, powerful mathematical approach to significantly improve the efficiency, accuracy and quality of data processing.

Publications

10 25 50
 
Description We have discovered (a) a new theory (called range space property-based theory) for sparse signal recovery between 2013-2015; (b) We have proposed a proximal Landweber Newton method and find applicaton to Lasso and image processing questions between 2014-2015; (c) We have discovered the connection between reweighted l1-method and sparsest solutions of compressed sensing problems based on classical linear programming theory (2014-2016); (d) we have developed an initial novel algorithms based on this connection and our experiments have indicated that our methods outperform many existing methods, and further improvement on both theory and performance of the algorithms are still ongoing. (e) The algorithm has been generalized to locate the sparsest point of polyhedral sets (2017). (f) A new stability theory has been developed for standand l1-minimization, and the assumption is milder than traditional ones (2015-2018). (g) The new stability of Dantzig selector and LASSO under RSP assumption were first established (2017-2018). (h) A new fast threshodling algorithms for compressed sensing problems have been developed (2017-2019) which transcend the traditional methods from both theoretical and numuercial point of view. The research is ongoing.
Exploitation Route The dicovered theory will be further studied and used by other researchers to carry out their researches in sparse signal recovery and mathematical optimization. Also, the developed algorithms will be further investigated and used by researchers in the above-mentioned areas and used by practioners working in signal and imaging prcessing. Part of our recent researches in this field have been used by many people across disciplines such as optimization and applied mathematics researcher, signal engineering, image and medical image processing. My research students and collaborators are continuing to undertake research based on the development from this project, for instance, dual algorithm and stability for genernal sparsity models, etc.
Sectors Digital/Communication/Information Technologies (including Software)

Education

Electronics

Financial Services

and Management Consultancy

Healthcare

URL https://doi.org/10.1287/moor.2016.0791
 
Description Our finding between 2012-2017 has been broadly used and cited in more than170 research papers or so (journals, conferences, dissertations) by various researchers in signal processing, optimization and management, computer science, comuter vision, medical imaging processing, and information science. Our findings on RSP-based theory dicovered between 2013-2014 have been used in research papers of some researchers in USA, China, UK, Hong Kong, and Germany. The researchers may use it to enhance or develop their own research in both theoy and computational method for signal and image recovery. The algorithms that we developed in 2014 (collaborated with researchers in Beijing, Birmingham and USA) are expected to bring remarkable impact in the coming years on both academic and software development. The algorithms developed in 2014 have been published in SIAM Journl on Optimization (2015), and have been published in Mathematics of Operations Research (2017). Both are the leading international journals. The stablity theory developed was accepted for publication in Mathematics of Operations Research in 2018, and the main research achievements out of the project were included in the monograph "Sparse Optimization Theorey and Methods" which was published in July 2018via CRC Press. Within 6 months since its publication, this book has been held in 67 libararies wordwide.
Sector Digital/Communication/Information Technologies (including Software),Education,Electronics,Financial Services, and Management Consultancy,Healthcare
Impact Types Economic

 
Title A new data sparse representation algorithm 
Description We prove that the sparsest representation of data can be reformulated as a bilevel optimization problem through which, a new design of sparsity seeking algorithm can be developed based on the interplay of sparsity in primal space and density in it dual space. The leads to a new methodology of the design of sparsity seeking algorithms. This idea and technology is entirely new and open a new research direction in the development of a new reweighted l1 algorithm together with related software development. 
Type Of Material Computer model/algorithm 
Year Produced 2014 
Provided To Others? Yes  
Impact We have been invited to give talks about our discovery on the proposed models and algorithms, at seminars, conference together with lectures at universities as well as collaborations. 
 
Description Cambridge (UK) 
Organisation University of Cambridge
Department Cambridge Judge Business School
Country United Kingdom 
Sector Academic/University 
PI Contribution We are jointly carrying out research in stability theorey of signal recovery algorithms, and we have achieved a new stability theory in this field, and our main results were summarized in a research paper in 2015 (was accepted for publication in the Journal: Mathematics of Oeprations Research). I have carried out the main research work. Currently, my 3 PhD students continue to work in the area and to further develop and refine our newly developed theory.
Collaborator Contribution Business school, Cambridge, UK) and Minnesota, USA undertook part of the research.
Impact A direct outcome of this collaboration is a new theorectical property (new stability theory) for signal recovery algorithms including basis pursuits, Dantzig selector, and statistical selction models such as LASSO. The developed new stablity theorem are significantly different from traditional ones in that our theorems are developed under the mildest assumptions and they do not reply on RIP or NSP assumption. And a new analytical tool has been developed for stablity analysis. This collaboration is multi-disciplinary, operational research, numerical optimimization, signal engineering, statistical and information sciences are involved.
Start Year 2014
 
Description Hong Kong 
Organisation Chinese University of Hong Kong
Country Hong Kong 
Sector Academic/University 
PI Contribution I was partially supported by CHUK in Hong Kong to visit and jointly carry out signal recovery research with their researchers in System Engineering department. I have been collaborated with their staff for a few years now.
Collaborator Contribution The CUHK in Hong Kong provides resources (Lab and financial support) for me to visit, discuss and carry out part of our joint research
Impact We have jointly published a research on SIAM Journal. The current research is still ongoing, and have not yet achieved our final goal, and will be in the near future. The collaboration is multi-disciplinary, involvinng system engineering, signal engineering and operations research.
Start Year 2012
 
Description Kyoto (Japan) 
Organisation University of Kyoto
Department Applied Maths and Physics
Country Japan 
Sector Academic/University 
PI Contribution I jointly worked on rank-optimization and published a research paper. I undertook the main research work.
Collaborator Contribution They discussed research issue with me, and undertook part of research work.
Impact with Kyoto, we have published a research paper in a Journal (Appl Math Comput).
Start Year 2013
 
Description Minnesota (USA) 
Organisation University of Minnesota
Country United States 
Sector Academic/University 
PI Contribution A researcher in Minnesota and me are jointly carrying out research in signal recovery algorithms, and we have finished a research paper in 2014. Our research Group at Birmingham untertook the main research work. A researcher in Minnesota undertook part of the research.
Collaborator Contribution Researchers in Minnesota undertook part of the research.
Impact An initial research outcome was achieved in 2013, and the final research results have been finished and submitted for publication in a journal (Math Oper Res), and we contunue our collaboration in 2014 and 2015, and the second research paper will be finished in spring 2015. This collaboration is multi-disciplinary, involving applied mathematics, signal engineering, optimization and operations research.
Start Year 2013
 
Description NSFC and BJUT (China) 
Organisation National Science Foundation China
Country China 
Sector Public 
PI Contribution Jointly prepare research proposal and carry out jointly research
Collaborator Contribution Jointly prepare research proposal and carry out jointly research
Impact One joint research work will be published in journal Comput Optim Appl (2015), and it is multi-disciplinary, and mathematics, operations research and image processing are involved
Start Year 2013
 
Description Academic Visit (Southampton) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Public/other audiences
Results and Impact Give 1hr talk about "Sparse Solutions to Underdetermined Linear Systems: Reweighted l1-Method" and discuss questions afterwards.


.

After my talk, some of the staff discussed the possible future research following my research, and asked my research papers for a further information, and wish Brimingham and Southampton to build a research collaboration in the future.
Year(s) Of Engagement Activity 2013
URL http://www.southampton.ac.uk/maths/news/seminars/archive.page?selected_group=2013/1
 
Description International Conference (iccopt2013) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact ZL (research fellow 1) attended this conference and gave a talk at the conference.

Duing this conference, ZL met and got to know many researchers, and shared his idea with them.
Year(s) Of Engagement Activity 2013
URL http://eventos.fct.unl.pt/iccopt2013
 
Description International Conference (ISORA 2013) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Type Of Presentation keynote/invited speaker
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Talk about my newly discovered theory "The sparsest solution to linear systems: RSP-based theory" which was out of this EPSRC research project, and discussed questions afterwards.



2. The same talk above was also given at Beijing Jiaotong University, Beijing, on 27 August, 2013.






.

After my talk, a lot of researchers from Chinese Academy of Sciences and other Universities asked if my research can be used to deal with signal with noises, and whether it is possible to use my theory to develope certain computational methods.
Year(s) Of Engagement Activity 2013
URL http://www.aporc.org/ISORA/2013/ISORA2013_Program.pdf
 
Description Invited lectures and organizing workshop (Chongqing, China) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Undergraduate students
Results and Impact I was invited and financially supported by Chongqing Education Ministry to organize an even/workshot lasting about 20 days in Chongqing, China. Based on Chongqing Jiaotong Unvisersity, to invite 5 external leading scientists to give research and new trend talks opened to general public, which has attracted 100 people to attend the talks. I also give intensive talks (6 lectures, each lasts 2 hrs) for undergraduate and postgraduate and university staff. The topics related to optimization, signal recovery, numerical analysis, network and imaging processing. Part of the talks are based on the research from this award. All activities during this even were filmed and recorded, which were used to other universities and research institutes later.
Year(s) Of Engagement Activity 2016
 
Description Plenary speaker in international conference in Applied and Computational Math 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Was invited to be a plenary speaker at the 2017 International Symposium on Computational and Applied Mathematics . The audience was from USA, China, UK, African, India, Iran and South Keroa.
Year(s) Of Engagement Activity 2017
URL http://www.engii.org/workshop/ISCAM/
 
Description Research Student (from Europe) 
Form Of Engagement Activity Participation in an open day or visit at my research institution
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Participants in your research and patient groups
Results and Impact LUKAS ADAM was invited to participate in part of research for two months. During his visit my research group, we regualarly discussed research questions from my current project. And he carried out a lot of numerical simulations for my developed algorithms.

After this visit, Lukas will continue to think and do research related to my current project.
Year(s) Of Engagement Activity 2014
 
Description Visit (Beijing Univ of Tech.) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact 2 hrs of talk on compressed sensing research questions, and a long discussion afterwards.

After my talk and discussion, a few researchers start to collaborate with me on their research questions. A few month later, we jointly published a research papers, and this collaboration is still alive.
Year(s) Of Engagement Activity 2014
 
Description Visit (CUHK, Hong Kong) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Talk compressed sensing quesstion and discuss afterwards, and also discuss possible future collaboration between my reserach group and CUHK group.

After my talk, researcher students and staff said they are very interested in the topic I had talked and they requested my related full research papers.
Year(s) Of Engagement Activity 2014
URL http://seminar.se.cuhk.edu.hk/content/efficiency-l1-minimization-solving-l0-minimization-problems-an...
 
Description Visit (JIaotong University, Beijing) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Schools
Results and Impact Seminar talk and discussion afterwards

After my talk, a few research staff told me they didn't releaze my introduced concept on "equvalence and strong equvalence" is so deep to understand the l1 and l0 problems. Two month later, they claimed that my talk has stimulated their research and made progress in that direction. My paper was used and cited in their new research paper. The school expected Birmingham and their University to further build research and exchange student relationship in the coming years.
Year(s) Of Engagement Activity 2013,2014
 
Description Visit (Warwick Universty) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Public/other audiences
Results and Impact Seminar talk and discussion before the seminar and afterwards, and exchange idea with a member of staff in buseness school at Warwick.

After my talk, members of staff asked if my idea can be extended to handle discrete optimization problem.
Year(s) Of Engagement Activity 2014
URL http://www2.warwick.ac.uk/fac/cross_fac/dimap/seminars/#110314Zhao
 
Description Visitor (Prof D Li, CUHK) 
Form Of Engagement Activity Participation in an open day or visit at my research institution
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Participants in your research and patient groups
Results and Impact I invited Professor D LI (CUHK, Hong Kong) to visit my insitution for 3 days during which we discussed the possible idea to develop theory and algorithms related to my current research project, and possible applications to cardinality constrained financial problems.

After his visit, we are planning to collaborate on developing algorithms for sparsity seeking problems, which is highly related to my current project.
Year(s) Of Engagement Activity 2014
 
Description Visitor (Prof D Sun, Singapore) 
Form Of Engagement Activity Participation in an open day or visit at my research institution
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Participants in your research and patient groups
Results and Impact I invited Professor D Sun (National Univ of Singapore) to come to visit my research group to discuss the algorithm theory for so-called ADM methods, which might be useful on my current research (l0-minimization problems).

After his visit, we plan to collaborate on some research question, like l0 and rank-problems
Year(s) Of Engagement Activity 2014
 
Description Worshop (Beijing) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Share and discuss research questions

I have met and discussed questions with colleagues from Minnesota, Stanford, Warwick, Chinese Academy, North Carolina, etc. The main purpose of this workshop is to maintain and/or build a good network in optimization and operations research fields.
Year(s) Of Engagement Activity 2014