{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/101492"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/101492","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Bilinear inverse problems with sparsity: Optimal identifiability conditions and efficient recovery","abstract":"Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, parsimonious structures of natural signals (e.g., subspace or sparsity) are exploited. However, there are few theoretical justifications for using such structures for BIPs. We consider two types of BIPs, blind deconvolution (BD) and blind gain and phase calibration (BGPC), with subspace or sparsity structures. Our contributions are twofold: we derive optimal identifiability conditions, and propose efficient algorithms that solve these problems. In previous work, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in $\\bbC^n$, with subspace constraints of dimensions $m_1$ and $m_2$, respectively, a sample complexity of $n\\geq m_1m_2$ is sufficient. This result is suboptimal, since the number of degrees of freedom is merely $m_1+m_2-1$. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In Chapter 2, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (resp. all pairs) of vectors in $\\bbC^n$, with sparsity constraints of sparsity levels $s_1$ and $s_2$, a sample complexity of $n > s_1+s_2$ (resp. $n > 2(s_1+s_2)$) is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in Chapter 2, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities. In previous work, we proposed studying the identifiability in bilinear inverse problems up to transformation groups. In particular, we studied several special cases of blind gain and phase calibration, including the cases of subspace and joint sparsity models on the signals, and gave sufficient and necessary conditions for identifiability up to certain transformation groups. However, there were gaps between the sample complexities in the sufficient conditions and the necessary conditions. In Chapter 3, under a mild assumption that the signals and models are generic, we bridge the gaps by deriving tight sufficient conditions with optimal or near optimal sample complexities. Recently there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In Chapter 4, we formulate BGPC as an eigenvalue/eigenvector problem, and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration (which we show is equivalent to a sparsity-projected gradient descent). Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. A problem related to BGPC is multichannel blind deconvolution (MBD) with a circular convolution model, i.e., the recovery of an unknown signal $f$ and multiple unknown filters $x_i$ from circular convolutions $y_i=x_i \\circledast f$ ($i=1,2,\\dots,N$). In Chapter 5, we consider the case where the $x_i$'s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse outputs $y_i\\circledast h$. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and $x_i$ using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.","abstract_html":"Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, parsimonious structures of natural signals (e.g., subspace or sparsity) are exploited. However, there are few theoretical justifications for using such structures for BIPs. We consider two types of BIPs, blind deconvolution (BD) and blind gain and phase calibration (BGPC), with subspace or sparsity structures. Our contributions are twofold: we derive optimal identifiability conditions, and propose efficient algorithms that solve these problems. In previous work, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in <span class=\"etd-inline-math\">\\bbC<sup>n</sup></span>, with subspace constraints of dimensions <span class=\"etd-inline-math\">m<sub>1</sub></span> and <span class=\"etd-inline-math\">m<sub>2</sub></span>, respectively, a sample complexity of <span class=\"etd-inline-math\">n\\geq m<sub>1</sub>m<sub>2</sub></span> is sufficient. This result is suboptimal, since the number of degrees of freedom is merely <span class=\"etd-inline-math\">m<sub>1</sub>+m<sub>2</sub>-1</span>. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In Chapter 2, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (resp. all pairs) of vectors in <span class=\"etd-inline-math\">\\bbC<sup>n</sup></span>, with sparsity constraints of sparsity levels <span class=\"etd-inline-math\">s<sub>1</sub></span> and <span class=\"etd-inline-math\">s<sub>2</sub></span>, a sample complexity of <span class=\"etd-inline-math\">n &gt; s<sub>1</sub>+s<sub>2</sub></span> (resp. <span class=\"etd-inline-math\">n &gt; 2(s<sub>1</sub>+s<sub>2</sub>)</span>) is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in Chapter 2, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities. In previous work, we proposed studying the identifiability in bilinear inverse problems up to transformation groups. In particular, we studied several special cases of blind gain and phase calibration, including the cases of subspace and joint sparsity models on the signals, and gave sufficient and necessary conditions for identifiability up to certain transformation groups. However, there were gaps between the sample complexities in the sufficient conditions and the necessary conditions. In Chapter 3, under a mild assumption that the signals and models are generic, we bridge the gaps by deriving tight sufficient conditions with optimal or near optimal sample complexities. Recently there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In Chapter 4, we formulate BGPC as an eigenvalue/eigenvector problem, and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration (which we show is equivalent to a sparsity-projected gradient descent). Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. A problem related to BGPC is multichannel blind deconvolution (MBD) with a circular convolution model, i.e., the recovery of an unknown signal $f$ and multiple unknown filters <span class=\"etd-inline-math\">x<sub>i</sub></span> from circular convolutions <span class=\"etd-inline-math\">y<sub>i</sub>=x<sub>i</sub> \\circledast f</span> ($i=1,2,\\dots,N$). In Chapter 5, we consider the case where the <span class=\"etd-inline-math\">x<sub>i</sub></span>&#x27;s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse outputs <span class=\"etd-inline-math\">y<sub>i</sub>\\circledast h</span>. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and <span class=\"etd-inline-math\">x<sub>i</sub></span> using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.","abstract_has_math":true,"creators":["Li, Yanjun"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Bresler, Yoram","Do, Minh","Milenkovic, Olgica","Moulin, Pierre","Romberg, Justin","Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-27T16:17:26Z","date_published":"2018-09-27T16:17:26Z","updated_at":"2026-07-22T22:24:40Z","subjects":["Bind calibration","Uniqueness","Sample complexity","Sensor array processing","Inverse rendering","Super-resolution fluorescence microscopy","Nonconvex optimization","Projected gradient descent","Manifold gradient descent","Strict saddle points","Blind deconvolution"],"languages":["en"],"rights":["Copyright 2018 Yanjun Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/101492","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Bresler, Yoram","Do, Minh","Milenkovic, Olgica","Moulin, Pierre","Romberg, Justin","Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Li, Yanjun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-27T16:17:26Z","2018-06-15","2018-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bind calibration","Uniqueness","Sample complexity","Sensor array processing","Inverse rendering","Super-resolution fluorescence microscopy","Nonconvex optimization","Projected gradient descent","Manifold gradient descent","Strict saddle points","Blind deconvolution"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Yanjun Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/101492"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, parsimonious structures of natural signals (e.g., subspace or sparsity) are exploited. However, there are few theoretical justifications for using such structures for BIPs. We consider two types of BIPs, blind deconvolution (BD) and blind gain and phase calibration (BGPC), with subspace or sparsity structures. Our contributions are twofold: we derive optimal identifiability conditions, and propose efficient algorithms that solve these problems. In previous work, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in $\\bbC^n$, with subspace constraints of dimensions $m_1$ and $m_2$, respectively, a sample complexity of $n\\geq m_1m_2$ is sufficient. This result is suboptimal, since the number of degrees of freedom is merely $m_1+m_2-1$. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In Chapter 2, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (resp. all pairs) of vectors in $\\bbC^n$, with sparsity constraints of sparsity levels $s_1$ and $s_2$, a sample complexity of $n > s_1+s_2$ (resp. $n > 2(s_1+s_2)$) is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in Chapter 2, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities. In previous work, we proposed studying the identifiability in bilinear inverse problems up to transformation groups. In particular, we studied several special cases of blind gain and phase calibration, including the cases of subspace and joint sparsity models on the signals, and gave sufficient and necessary conditions for identifiability up to certain transformation groups. However, there were gaps between the sample complexities in the sufficient conditions and the necessary conditions. In Chapter 3, under a mild assumption that the signals and models are generic, we bridge the gaps by deriving tight sufficient conditions with optimal or near optimal sample complexities. Recently there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In Chapter 4, we formulate BGPC as an eigenvalue/eigenvector problem, and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration (which we show is equivalent to a sparsity-projected gradient descent). Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. A problem related to BGPC is multichannel blind deconvolution (MBD) with a circular convolution model, i.e., the recovery of an unknown signal $f$ and multiple unknown filters $x_i$ from circular convolutions $y_i=x_i \\circledast f$ ($i=1,2,\\dots,N$). In Chapter 5, we consider the case where the $x_i$'s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse outputs $y_i\\circledast h$. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and $x_i$ using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Yanjun Li, accepted the attached license on 2018-06-14 at 23:09.","The student, Yanjun Li, submitted this Dissertation for approval on 2018-06-14 at 23:25.","This Dissertation was approved for publication on 2018-06-15 at 10:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12632 on 2018-09-27 at 10:44:49","Made available in DSpace on 2018-09-27T16:17:26Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2018.pdf: 2582005 bytes, checksum: f3cfea65b2c5e9503fbf5a20cc2db96f (MD5) LICENSE.txt: 4206 bytes, checksum: 6bf78acc972c0fff3d3e255aa596fd06 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: 532a2a15e19871bbf726f72e314b271a (MD5) Previous issue date: 2018-06-15"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Bilinear inverse problems with sparsity: Optimal identifiability conditions and efficient recovery"]}]}],"canonical_facts":{"dc:contributor":["Bresler, Yoram","Do, Minh","Milenkovic, Olgica","Moulin, Pierre","Romberg, Justin","Srikant, Rayadurgam"],"dc:creator":["Li, Yanjun"],"dc:date":["2018-09-27T16:17:26Z","2018-06-15","2018-08"],"dc:description":["Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, parsimonious structures of natural signals (e.g., subspace or sparsity) are exploited. However, there are few theoretical justifications for using such structures for BIPs. We consider two types of BIPs, blind deconvolution (BD) and blind gain and phase calibration (BGPC), with subspace or sparsity structures. Our contributions are twofold: we derive optimal identifiability conditions, and propose efficient algorithms that solve these problems. In previous work, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in $\\bbC^n$, with subspace constraints of dimensions $m_1$ and $m_2$, respectively, a sample complexity of $n\\geq m_1m_2$ is sufficient. This result is suboptimal, since the number of degrees of freedom is merely $m_1+m_2-1$. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In Chapter 2, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (resp. all pairs) of vectors in $\\bbC^n$, with sparsity constraints of sparsity levels $s_1$ and $s_2$, a sample complexity of $n > s_1+s_2$ (resp. $n > 2(s_1+s_2)$) is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in Chapter 2, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities. In previous work, we proposed studying the identifiability in bilinear inverse problems up to transformation groups. In particular, we studied several special cases of blind gain and phase calibration, including the cases of subspace and joint sparsity models on the signals, and gave sufficient and necessary conditions for identifiability up to certain transformation groups. However, there were gaps between the sample complexities in the sufficient conditions and the necessary conditions. In Chapter 3, under a mild assumption that the signals and models are generic, we bridge the gaps by deriving tight sufficient conditions with optimal or near optimal sample complexities. Recently there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In Chapter 4, we formulate BGPC as an eigenvalue/eigenvector problem, and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration (which we show is equivalent to a sparsity-projected gradient descent). Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. A problem related to BGPC is multichannel blind deconvolution (MBD) with a circular convolution model, i.e., the recovery of an unknown signal $f$ and multiple unknown filters $x_i$ from circular convolutions $y_i=x_i \\circledast f$ ($i=1,2,\\dots,N$). In Chapter 5, we consider the case where the $x_i$'s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse outputs $y_i\\circledast h$. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and $x_i$ using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Yanjun Li, accepted the attached license on 2018-06-14 at 23:09.","The student, Yanjun Li, submitted this Dissertation for approval on 2018-06-14 at 23:25.","This Dissertation was approved for publication on 2018-06-15 at 10:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12632 on 2018-09-27 at 10:44:49","Made available in DSpace on 2018-09-27T16:17:26Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2018.pdf: 2582005 bytes, checksum: f3cfea65b2c5e9503fbf5a20cc2db96f (MD5) LICENSE.txt: 4206 bytes, checksum: 6bf78acc972c0fff3d3e255aa596fd06 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: 532a2a15e19871bbf726f72e314b271a (MD5) Previous issue date: 2018-06-15"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/101492"],"dc:language":["en"],"dc:rights":["Copyright 2018 Yanjun Li"],"dc:subject":["Bind calibration","Uniqueness","Sample complexity","Sensor array processing","Inverse rendering","Super-resolution fluorescence microscopy","Nonconvex optimization","Projected gradient descent","Manifold gradient descent","Strict saddle points","Blind deconvolution"],"dc:title":["Bilinear inverse problems with sparsity: Optimal identifiability conditions and efficient recovery"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:40Z"}