Overcomplete tensor decomposition via convex optimization

Qiuwei Li, Ashley Prater, Lixin Shen, Gongguo Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

Abstract

This work develops theories and computational methods for overcomplete, non-orthogonal tensor decomposition using convex optimization. Under an incoherence condition of the rank-one factors, we show that one can retrieve tensor decomposition by solving a convex, infinite-dimensional analog of ℓ1 minimization on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Two computational schemes are proposed to solve the infinite-dimensional optimization: semidefinite programs based on sum-of-squares relaxations and nonlinear programs that are an exact reformulation of the tensor nuclear norm. The latter exhibits superior performance compared with the state-of-the-art tensor decomposition methods.

Original languageEnglish (US)
Title of host publication2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages53-56
Number of pages4
ISBN (Print)9781479919635
DOIs
StatePublished - Jan 14 2016
Event6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015 - Cancun, Mexico
Duration: Dec 13 2015Dec 16 2015

Other

Other6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015
CountryMexico
CityCancun
Period12/13/1512/16/15

Fingerprint

Tensor Decomposition
Convex optimization
Convex Optimization
Tensors
Decomposition
Tensor
Norm
Semidefinite Program
Optimization
Sum of squares
Decomposition Method
Reformulation
Computational Methods
Analogue
Computational methods

ASJC Scopus subject areas

  • Signal Processing
  • Computational Mathematics

Cite this

Li, Q., Prater, A., Shen, L., & Tang, G. (2016). Overcomplete tensor decomposition via convex optimization. In 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015 (pp. 53-56). [7383734] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CAMSAP.2015.7383734

Overcomplete tensor decomposition via convex optimization. / Li, Qiuwei; Prater, Ashley; Shen, Lixin; Tang, Gongguo.

2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015. Institute of Electrical and Electronics Engineers Inc., 2016. p. 53-56 7383734.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Li, Q, Prater, A, Shen, L & Tang, G 2016, Overcomplete tensor decomposition via convex optimization. in 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015., 7383734, Institute of Electrical and Electronics Engineers Inc., pp. 53-56, 6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015, Cancun, Mexico, 12/13/15. https://doi.org/10.1109/CAMSAP.2015.7383734
Li Q, Prater A, Shen L, Tang G. Overcomplete tensor decomposition via convex optimization. In 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015. Institute of Electrical and Electronics Engineers Inc. 2016. p. 53-56. 7383734 https://doi.org/10.1109/CAMSAP.2015.7383734
Li, Qiuwei ; Prater, Ashley ; Shen, Lixin ; Tang, Gongguo. / Overcomplete tensor decomposition via convex optimization. 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 53-56
@inproceedings{24bb02b4d50f4c9881c8a4dfc4e74912,
title = "Overcomplete tensor decomposition via convex optimization",
abstract = "This work develops theories and computational methods for overcomplete, non-orthogonal tensor decomposition using convex optimization. Under an incoherence condition of the rank-one factors, we show that one can retrieve tensor decomposition by solving a convex, infinite-dimensional analog of ℓ1 minimization on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Two computational schemes are proposed to solve the infinite-dimensional optimization: semidefinite programs based on sum-of-squares relaxations and nonlinear programs that are an exact reformulation of the tensor nuclear norm. The latter exhibits superior performance compared with the state-of-the-art tensor decomposition methods.",
author = "Qiuwei Li and Ashley Prater and Lixin Shen and Gongguo Tang",
year = "2016",
month = "1",
day = "14",
doi = "10.1109/CAMSAP.2015.7383734",
language = "English (US)",
isbn = "9781479919635",
pages = "53--56",
booktitle = "2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - GEN

T1 - Overcomplete tensor decomposition via convex optimization

AU - Li, Qiuwei

AU - Prater, Ashley

AU - Shen, Lixin

AU - Tang, Gongguo

PY - 2016/1/14

Y1 - 2016/1/14

N2 - This work develops theories and computational methods for overcomplete, non-orthogonal tensor decomposition using convex optimization. Under an incoherence condition of the rank-one factors, we show that one can retrieve tensor decomposition by solving a convex, infinite-dimensional analog of ℓ1 minimization on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Two computational schemes are proposed to solve the infinite-dimensional optimization: semidefinite programs based on sum-of-squares relaxations and nonlinear programs that are an exact reformulation of the tensor nuclear norm. The latter exhibits superior performance compared with the state-of-the-art tensor decomposition methods.

AB - This work develops theories and computational methods for overcomplete, non-orthogonal tensor decomposition using convex optimization. Under an incoherence condition of the rank-one factors, we show that one can retrieve tensor decomposition by solving a convex, infinite-dimensional analog of ℓ1 minimization on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Two computational schemes are proposed to solve the infinite-dimensional optimization: semidefinite programs based on sum-of-squares relaxations and nonlinear programs that are an exact reformulation of the tensor nuclear norm. The latter exhibits superior performance compared with the state-of-the-art tensor decomposition methods.

UR - http://www.scopus.com/inward/record.url?scp=84963861012&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963861012&partnerID=8YFLogxK

U2 - 10.1109/CAMSAP.2015.7383734

DO - 10.1109/CAMSAP.2015.7383734

M3 - Conference contribution

SN - 9781479919635

SP - 53

EP - 56

BT - 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -