uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On some sparsity related problems and the randomized Kaczmarz algorithm
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Systems and Control. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Automatic control.
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis studies several problems related to recovery and estimation. Specifically, these problems are about sparsity and low-rankness, and the randomized Kaczmarz algorithm. This thesis includes four papers referred to as Paper A, Paper B, Paper C, and Paper D.

Paper A considers how to make use of the fact that the solution to an overdetermined system is sparse. This paper presents a three-stage approach to accomplish the task. We show that this strategy, under the assumptions as made in the paper, achieves the oracle property.

In Paper B, a Hankel-matrix completion problem arising in system theory is studied. The use of the nuclear norm heuristic for this basic problem is considered. Theoretical justification for the case of a single real pole is given. Results show that for the case of a single real pole, the nuclear norm heuristic succeeds in the matrix completion task. Numerical simulations indicate that this result does not always carry over to the case of two real poles.

Paper C discusses a screening approach for improving the computational performance of the Basis Pursuit De-Noising problem. The key ingredient for this work is to make use of an efficient ellipsoid update algorithm. The results of the experiments show that the proposed scheme can improve the overall time complexity for solving the problem.

Paper D studies the choice of the probability distribution for implementing the row-projections in the randomized Kaczmarz algorithm. This relates to an open question in the recent literature. The result proves that a probability distribution resulting in a faster convergence of the algorithm can be found by solving a related Semi-Definite Programming optimization problem.

Place, publisher, year, edition, pages
Uppsala University, 2014.
Series
Information technology licentiate theses: Licentiate theses from the Department of Information Technology, ISSN 1404-5117 ; 2014-003
National Category
Signal Processing
Research subject
Electrical Engineering with specialization in Signal Processing
Identifiers
URN: urn:nbn:se:uu:diva-226198OAI: oai:DiVA.org:uu-226198DiVA: diva2:724553
Presentation
2014-04-09, Room 2347, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 10:15 (English)
Supervisors
Available from: 2014-04-09 Created: 2014-06-12 Last updated: 2017-08-31Bibliographically approved
List of papers
1. Sparse estimation from noisy observations of an overdetermined linear system
Open this publication in new window or tab >>Sparse estimation from noisy observations of an overdetermined linear system
2014 (English)In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 50, no 11, 2845-2851 p.Article in journal (Refereed) Published
National Category
Signal Processing
Identifiers
urn:nbn:se:uu:diva-226192 (URN)10.1016/j.automatica.2014.08.018 (DOI)000345727700010 ()
Available from: 2014-10-07 Created: 2014-06-12 Last updated: 2017-12-05Bibliographically approved
2. On the nuclear norm heuristic for a Hankel matrix completion problem
Open this publication in new window or tab >>On the nuclear norm heuristic for a Hankel matrix completion problem
2015 (English)In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 51, 268-272 p.Article in journal (Refereed) Published
Abstract [en]

This note addresses the question if and why the nuclear norm heuristic can recover an impulse response generated by a stable single-real-pole system, if elements of the upper-triangle of the associated Hankel matrix are given. Since the setting is deterministic, theories based on stochastic assumptions for low-rank matrix recovery do not apply in the considered situation. A 'certificate' which guarantees the success of the matrix completion task is constructed by exploring the structural information of the hidden matrix. Experimental results and discussions regarding the nuclear norm heuristic applied to a more general setting are also given.

National Category
Control Engineering
Identifiers
urn:nbn:se:uu:diva-226193 (URN)10.1016/j.automatica.2014.10.045 (DOI)000348015500032 ()
Available from: 2014-10-29 Created: 2014-06-12 Last updated: 2017-12-05Bibliographically approved
3. An ellipsoid based, two-stage screening test for BPDN
Open this publication in new window or tab >>An ellipsoid based, two-stage screening test for BPDN
2012 (English)In: Proc. 20th European Signal Processing Conference, IEEE , 2012, 654-658 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE, 2012
National Category
Signal Processing
Identifiers
urn:nbn:se:uu:diva-183856 (URN)978-1-4673-1068-0 (ISBN)
Conference
EUSIPCO 2012, August 27-31, Bucharest, Romania
Available from: 2012-08-31 Created: 2012-11-05 Last updated: 2014-06-12Bibliographically approved
4. On the randomized Kaczmarz algorithm
Open this publication in new window or tab >>On the randomized Kaczmarz algorithm
2014 (English)In: IEEE Signal Processing Letters, ISSN 1070-9908, E-ISSN 1558-2361, Vol. 21, no 3, 330-333 p.Article in journal (Refereed) Published
National Category
Signal Processing
Identifiers
urn:nbn:se:uu:diva-211501 (URN)10.1109/LSP.2013.2294376 (DOI)000331299200004 ()
Available from: 2014-01-31 Created: 2013-11-25 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

fulltext(840 kB)202 downloads
File information
File name FULLTEXT01.pdfFile size 840 kBChecksum SHA-512
b88aa999ac3510c1f89a3c3fa946b8734eb98187a97a89cc3429e72035772b3bfde8eb37d756e9fba49e0094d1aee82a276607618c0681e99bf5a206b6e6920e
Type fulltextMimetype application/pdf

Authority records BETA

Dai, Liang

Search in DiVA

By author/editor
Dai, Liang
By organisation
Division of Systems and ControlAutomatic control
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar
Total: 202 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 480 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf