{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108074"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108074","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel Gauss-Newton method for CP decomposition","abstract":"In this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.","abstract_html":"In this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.","abstract_has_math":false,"creators":["Singh, Navjot"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Applied Mathematics","degree_department":null,"school":null,"contributors":["Solomonik, Edgar"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T21:58:11Z","date_published":"2020-08-26T21:58:11Z","updated_at":"2026-07-22T22:24:47Z","subjects":["tensor decompositions, canonical decomposition (CANDECOMP),Gauss Newton"],"languages":["en"],"rights":["Copyright 2020 Navjot Singh"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108074","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Solomonik, Edgar"]},{"key":"dc:creator","label":"Author","values":["Singh, Navjot"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T21:58:11Z","2020-05-15","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Applied Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["tensor decompositions, canonical decomposition (CANDECOMP),Gauss Newton"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Navjot Singh"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108074"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Navjot Singh, accepted the attached license on 2020-05-15 at 16:46.","The student, Navjot Singh, submitted this Thesis for approval on 2020-05-15 at 16:46.","This Thesis was approved for publication on 2020-05-15 at 16:54.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15413 on 2020-08-25 at 17:15:10","Made available in DSpace on 2020-08-26T21:58:11Z (GMT). No. of bitstreams: 2 SINGH-THESIS-2020.pdf: 693088 bytes, checksum: cb5a4f67a28b2af4497e31dae9b31510 (MD5) LICENSE.txt: 4209 bytes, checksum: ccac5fa6be0f108bec87e0dea75d1383 (MD5) Previous issue date: 2020-05-15"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Parallel Gauss-Newton method for CP decomposition"]}]}],"canonical_facts":{"dc:contributor":["Solomonik, Edgar"],"dc:creator":["Singh, Navjot"],"dc:date":["2020-08-26T21:58:11Z","2020-05-15","2020-05"],"dc:description":["In this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Navjot Singh, accepted the attached license on 2020-05-15 at 16:46.","The student, Navjot Singh, submitted this Thesis for approval on 2020-05-15 at 16:46.","This Thesis was approved for publication on 2020-05-15 at 16:54.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15413 on 2020-08-25 at 17:15:10","Made available in DSpace on 2020-08-26T21:58:11Z (GMT). No. of bitstreams: 2 SINGH-THESIS-2020.pdf: 693088 bytes, checksum: cb5a4f67a28b2af4497e31dae9b31510 (MD5) LICENSE.txt: 4209 bytes, checksum: ccac5fa6be0f108bec87e0dea75d1383 (MD5) Previous issue date: 2020-05-15"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108074"],"dc:language":["en"],"dc:rights":["Copyright 2020 Navjot Singh"],"dc:subject":["tensor decompositions, canonical decomposition (CANDECOMP),Gauss Newton"],"dc:title":["Parallel Gauss-Newton method for CP decomposition"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Applied Mathematics"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:47Z"}