On Approximation Algorithm for Orthogonal Low-Rank Tensor Approximation View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-06-28

AUTHORS

Yuning Yang

ABSTRACT

This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797–1825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm. More... »

PAGES

821-851

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10957-022-02050-x

DOI

http://dx.doi.org/10.1007/s10957-022-02050-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1149027050


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "College of Mathematics and Information Science, Guangxi University, 530004, Nanning, China", 
          "id": "http://www.grid.ac/institutes/grid.256609.e", 
          "name": [
            "College of Mathematics and Information Science, Guangxi University, 530004, Nanning, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Yuning", 
        "id": "sg:person.01322657357.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01322657357.03"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00211-018-0981-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105642711", 
          "https://doi.org/10.1007/s00211-018-0981-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-014-0774-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042371681", 
          "https://doi.org/10.1007/s10107-014-0774-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-010-0409-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051989927", 
          "https://doi.org/10.1007/s10107-010-0409-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-011-0464-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026016702", 
          "https://doi.org/10.1007/s10107-011-0464-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10898-017-0561-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091419683", 
          "https://doi.org/10.1007/s10898-017-0561-6"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-06-28", 
    "datePublishedReg": "2022-06-28", 
    "description": "This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797\u20131825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10957-022-02050-x", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.8892206", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1044187", 
        "issn": [
          "0022-3239", 
          "1573-2878"
        ], 
        "name": "Journal of Optimization Theory and Applications", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "194"
      }
    ], 
    "keywords": [
      "approximation algorithm", 
      "low-rank tensor approximation", 
      "rank-1 terms", 
      "singular value decomposition", 
      "approximation type", 
      "tensor approximation", 
      "problem data", 
      "joint singular value decomposition", 
      "R rank", 
      "iterative type", 
      "solution method", 
      "approximation", 
      "approximation ratio", 
      "value decomposition", 
      "key subproblem", 
      "tensor", 
      "existing algorithms", 
      "numerical study", 
      "algorithm", 
      "subproblems", 
      "problem", 
      "deterministic", 
      "latent factors", 
      "computation", 
      "independent component analysis", 
      "orthogonality", 
      "multilinearity", 
      "image processing", 
      "sum", 
      "Yang", 
      "coincide", 
      "rank", 
      "decomposition", 
      "terms", 
      "component analysis", 
      "work", 
      "applications", 
      "number", 
      "types", 
      "cases", 
      "gap", 
      "results", 
      "size", 
      "usefulness", 
      "analysis", 
      "processing", 
      "data", 
      "literature", 
      "ratio", 
      "factors", 
      "senses", 
      "study", 
      "method"
    ], 
    "name": "On Approximation Algorithm for Orthogonal Low-Rank Tensor Approximation", 
    "pagination": "821-851", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1149027050"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10957-022-02050-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10957-022-02050-x", 
      "https://app.dimensions.ai/details/publication/pub.1149027050"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:49", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_928.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10957-022-02050-x"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02050-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02050-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02050-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02050-x'


 

This table displays all metadata directly associated to this object as RDF triples.

132 TRIPLES      21 PREDICATES      82 URIs      69 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10957-022-02050-x schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Ne1543ba0a33f496e8ebd62baac7957ea
4 schema:citation sg:pub.10.1007/s00211-018-0981-3
5 sg:pub.10.1007/s10107-010-0409-z
6 sg:pub.10.1007/s10107-011-0464-0
7 sg:pub.10.1007/s10107-014-0774-0
8 sg:pub.10.1007/s10898-017-0561-6
9 schema:datePublished 2022-06-28
10 schema:datePublishedReg 2022-06-28
11 schema:description This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797–1825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm.
12 schema:genre article
13 schema:isAccessibleForFree true
14 schema:isPartOf N7306e33e801c4d78b72378454417a7c6
15 N99017e95ad3f4d4e8d4b33019d18daa3
16 sg:journal.1044187
17 schema:keywords R rank
18 Yang
19 algorithm
20 analysis
21 applications
22 approximation
23 approximation algorithm
24 approximation ratio
25 approximation type
26 cases
27 coincide
28 component analysis
29 computation
30 data
31 decomposition
32 deterministic
33 existing algorithms
34 factors
35 gap
36 image processing
37 independent component analysis
38 iterative type
39 joint singular value decomposition
40 key subproblem
41 latent factors
42 literature
43 low-rank tensor approximation
44 method
45 multilinearity
46 number
47 numerical study
48 orthogonality
49 problem
50 problem data
51 processing
52 rank
53 rank-1 terms
54 ratio
55 results
56 senses
57 singular value decomposition
58 size
59 solution method
60 study
61 subproblems
62 sum
63 tensor
64 tensor approximation
65 terms
66 types
67 usefulness
68 value decomposition
69 work
70 schema:name On Approximation Algorithm for Orthogonal Low-Rank Tensor Approximation
71 schema:pagination 821-851
72 schema:productId N431a84bc393b41b48c35218d3972505a
73 Nb9d0e0efad6542569a9ad0048708115c
74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149027050
75 https://doi.org/10.1007/s10957-022-02050-x
76 schema:sdDatePublished 2022-10-01T06:49
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher N6dd65ca8162840308ea8d8c169059f40
79 schema:url https://doi.org/10.1007/s10957-022-02050-x
80 sgo:license sg:explorer/license/
81 sgo:sdDataset articles
82 rdf:type schema:ScholarlyArticle
83 N431a84bc393b41b48c35218d3972505a schema:name doi
84 schema:value 10.1007/s10957-022-02050-x
85 rdf:type schema:PropertyValue
86 N6dd65ca8162840308ea8d8c169059f40 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N7306e33e801c4d78b72378454417a7c6 schema:volumeNumber 194
89 rdf:type schema:PublicationVolume
90 N99017e95ad3f4d4e8d4b33019d18daa3 schema:issueNumber 3
91 rdf:type schema:PublicationIssue
92 Nb9d0e0efad6542569a9ad0048708115c schema:name dimensions_id
93 schema:value pub.1149027050
94 rdf:type schema:PropertyValue
95 Ne1543ba0a33f496e8ebd62baac7957ea rdf:first sg:person.01322657357.03
96 rdf:rest rdf:nil
97 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
98 schema:name Mathematical Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Numerical and Computational Mathematics
102 rdf:type schema:DefinedTerm
103 sg:grant.8892206 http://pending.schema.org/fundedItem sg:pub.10.1007/s10957-022-02050-x
104 rdf:type schema:MonetaryGrant
105 sg:journal.1044187 schema:issn 0022-3239
106 1573-2878
107 schema:name Journal of Optimization Theory and Applications
108 schema:publisher Springer Nature
109 rdf:type schema:Periodical
110 sg:person.01322657357.03 schema:affiliation grid-institutes:grid.256609.e
111 schema:familyName Yang
112 schema:givenName Yuning
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01322657357.03
114 rdf:type schema:Person
115 sg:pub.10.1007/s00211-018-0981-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105642711
116 https://doi.org/10.1007/s00211-018-0981-3
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/s10107-010-0409-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1051989927
119 https://doi.org/10.1007/s10107-010-0409-z
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/s10107-011-0464-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026016702
122 https://doi.org/10.1007/s10107-011-0464-0
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/s10107-014-0774-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042371681
125 https://doi.org/10.1007/s10107-014-0774-0
126 rdf:type schema:CreativeWork
127 sg:pub.10.1007/s10898-017-0561-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091419683
128 https://doi.org/10.1007/s10898-017-0561-6
129 rdf:type schema:CreativeWork
130 grid-institutes:grid.256609.e schema:alternateName College of Mathematics and Information Science, Guangxi University, 530004, Nanning, China
131 schema:name College of Mathematics and Information Science, Guangxi University, 530004, Nanning, China
132 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...