13.3.8.7 Computational Complexity Issues

Chapter Contents (Back)
Computational Complexity. Complexity. Mostly computational issues, not so the issue of vision as a complex task. Graph matchin complexity is generally under graph matching.

Miller, R.E., and Thather, J.W., (Eds.),
Complexity of Computer Computation,
Indexed as CCComp1972. BibRef 7200

Boult, T.E.,
Optimal Algorithms: Tools for Mathematical Modeling,
Complexity(3), 1987, pp. 183-200. BibRef 8700
And:
Using Optimal Algorithms to Test Model Assumptions in Computer Vision,
DARPA87(921-926). BibRef

Boult, T.E.,
What is Regular in Regularization?,
ICCV87(457-462). A look at regularization and some alternatives. BibRef 8700

Perlovsky, L.I.,
Conundrum of Combinatorial Complexity,
PAMI(20), No. 6, June 1998, pp. 666-670.
IEEE DOI 9807
BibRef

Falelakis, M., Diou, C., Delopoulos, A.,
Semantic Identification: Balancing between Complexity and Validity,
JASP(2006), No. 1, January 2006, pp. 1-12.
WWW Link. 0603
BibRef

Alexeev, B., Ward, R.,
On the Complexity of Mumford-Shah-Type Regularization, Viewed as a Relaxed Sparsity Constraint,
IP(19), No. 10, October 2010, pp. 2787-2789.
IEEE DOI 1003
Inverse problems are NP-hard in general unlike Mumford-Shah functional, thus it can't solve them exactly. BibRef

Prusa, D.[Daniel], Werner, T.[Toma],
Universality of the Local Marginal Polytope,
PAMI(37), No. 4, April 2015, pp. 898-904.
IEEE DOI 1503
BibRef
Earlier: CVPR13(1738-1743)
IEEE DOI 1309
Complexity theory. min-sum problem, energy minimization. BibRef

Marangoni-Simonsen, D., Xie, Y.[Yao],
Sequential Changepoint Approach for Online Community Detection,
SPLetters(22), No. 8, August 2015, pp. 1035-1039.
IEEE DOI 1502
computational complexity BibRef

Liang, S., Luo, J., Liu, W., Wei, Y.,
Sketch Matching on Topology Product Graph,
PAMI(37), No. 8, August 2015, pp. 1723-1729.
IEEE DOI 1507
Complexity theory BibRef

Yin, H.B., Yang, E., Yu, X., Xia, Z.,
Fast Soft Decision Quantization With Adaptive Preselection and Dynamic Trellis Graph,
CirSysVideo(25), No. 8, August 2015, pp. 1362-1375.
IEEE DOI 1508
Complexity theory BibRef

Humeau-Heurtier, A.[Anne], Wu, C.W.[Chiu-Wen], Wu, S.D.[Shuen-De],
Refined Composite Multiscale Permutation Entropy to Overcome Multiscale Permutation Entropy Length Dependence,
SPLetters(22), No. 12, December 2015, pp. 2364-2367.
IEEE DOI 1512
computational complexity BibRef

Azami, H.[Hamed], Escudero, J., Humeau-Heurtier, A.[Anne],
Bidimensional Distribution Entropy to Analyze the Irregularity of Small-Sized Textures,
SPLetters(24), No. 9, September 2017, pp. 1338-1342.
IEEE DOI 1708
Algorithm design and analysis, Databases, Entropy, Surface texture, Surface treatment, Bidimensional dispersion entropy, irregularity, texture analysis, two-dimensional, BibRef

Azami, H.[Hamed], Virgilio da Silva, L.E.[Luiz Eduardo], Omoto, A.C.M.[Ana Carolina Mieko], Humeau-Heurtier, A.[Anne],
Two-dimensional dispersion entropy: An information-theoretic method for irregularity analysis of images,
SP:IC(75), 2019, pp. 178-187.
Elsevier DOI 1906
Biomedical image processing, Texture analysis, Irregularity, Two-dimensional dispersion entropy, Two-dimensional sample entropy BibRef

McEwen, J.D., Buttner, M., Leistedt, B., Peiris, H.V., Wiaux, Y.,
A Novel Sampling Theorem on the Rotation Group,
SPLetters(22), No. 12, December 2015, pp. 2425-2429.
IEEE DOI 1512
computational complexity BibRef

Ewert, W., Dembski, W.A., Marks, R.J.,
Measuring Meaningful Information in Images: Algorithmic Specified Complexity,
IET-CV(9), No. 6, 2015, pp. 884-894.
DOI Link 1512
computational complexity BibRef

Zhang, D., Matthé, M., Mendes, L.L., Fettweis, G.,
Message Passing Algorithms for Upper and Lower Bounding the Coded Modulation Capacity in a Large-Scale Linear System,
SPLetters(23), No. 4, April 2016, pp. 537-540.
IEEE DOI 1604
Complexity theory BibRef

Schoenecker, S., Luginbuhl, T.,
Characteristic Functions of the Product of Two Gaussian Random Variables and the Product of a Gaussian and a Gamma Random Variable,
SPLetters(23), No. 5, May 2016, pp. 644-647.
IEEE DOI 1604
Convolution BibRef

Ocegueda, O.[Omar], Dalmau, O.[Oscar], Garyfallidis, E.[Eleftherios], Descoteaux, M.[Maxime], Rivera, M.[Mariano],
On the computation of integrals over fixed-size rectangles of arbitrary dimension,
PRL(79), No. 1, 2016, pp. 68-72.
Elsevier DOI 1608
Integral Image BibRef

Aspelmeier, T.[Timo], Charitha, C., Luke, D.R.[D. Russell],
Local Linear Convergence of the ADMM/Douglas-Rachford Algorithms without Strong Convexity and Application to Statistical Imaging,
SIIMS(9), No. 2, 2016, pp. 842-868.
DOI Link 1608
BibRef

Weickert, J.[Joachim], Grewenig, S.[Sven], Schroers, C.[Christopher], Bruhn, A.[Andrés],
Cyclic Schemes for PDE-Based Image Analysis,
IJCV(118), No. 3, July 2016, pp. 275-299.
Springer DOI 1608
Efficient algorithms for PDEs in computer vision. Diffusion, optimization. BibRef

Chi, Y., Lu, Y.M.,
Kaczmarz Method for Solving Quadratic Equations,
SPLetters(23), No. 9, September 2016, pp. 1183-1187.
IEEE DOI 1609
Gaussian processes BibRef

Maya, J.A., Vega, L.R., Galarza, C.G.,
A Closed-Form Approximation for the CDF of the Sum of Independent Random Variables,
SPLetters(24), No. 1, January 2017, pp. 121-125.
IEEE DOI 1702
approximation theory BibRef

El Moataz, A.[Abderrahim], Lozes, F.[François], Toutain, M.[Matthieu],
Nonlocal PDEs on Graphs: From Tug-of-War Games to Unified Interpolation on Images and Point Clouds,
JMIV(57), No. 3, March 2017, pp. 381-401.
Springer DOI 1702
BibRef

Masiero, B.[Bruno], Nascimento, V.H.[Vítor H.],
Revisiting the Kronecker Array Transform,
SPLetters(24), No. 5, May 2017, pp. 525-529.
IEEE DOI 1704
array signal processing. Calculation of a matrix-vector product. BibRef

Jiao, Y.L.[Yu-Ling], Jin, B.[Bangti], Lu, X.L.[Xi-Liang],
Iterative Soft/Hard Thresholding With Homotopy Continuation for Sparse Recovery,
SPLetters(24), No. 6, June 2017, pp. 784-788.
IEEE DOI 1705
Continuation, convergence, iterative soft/hard thresholding (IST/IHT), solution, path BibRef

Cui, G., Fu, Y., Yu, X., Li, J.,
Local Ambiguity Function Shaping via Unimodular Sequence Design,
SPLetters(24), No. 7, July 2017, pp. 977-981.
IEEE DOI 1706
computational complexity, gradient methods, optimisation, radar detection, AISO algorithm, WISL, accelerated iterative sequential optimization algorithm, computational complexity, gradient method, high-speed target detection, local ambiguity function shaping, radar system, range bins, specific Doppler bins, unimodular sequence design, weighted integrated sidelobe level, Accelerated iterative sequential optimization (AISO), local ambiguity function, unimodular, sequence BibRef

Pyatkin, A.[Artem], Aloise, D.[Daniel], Mladenovic, N.[Nenad],
NP-Hardness of balanced minimum sum-of-squares clustering,
PRL(97), No. 1, 2017, pp. 44-45.
Elsevier DOI 1709
Balanced clustering BibRef

Pustelnik, N.[Nelly], Condat, L.[Laurent],
Proximity Operator of a Sum of Functions; Application to Depth Map Estimation,
SPLetters(24), No. 12, December 2017, pp. 1827-1831.
IEEE DOI 1712
convex programming, graph theory, image processing, optimisation, convex optimization, depth map estimation, image processing, support function BibRef

Yadav, D.K.[Devendra Kumar], Kuldeep, G.[Gajraj], Joshi, S.D.,
Ramanujan Sums as Derivatives and Applications,
SPLetters(25), No. 3, March 2018, pp. 413-416.
IEEE DOI 1802
Estimation, Image edge detection, Kernel, Noise level, Presses, Signal processing, Discrete fourier transform, BibRef

Radhika, S., Sivabalan, A.,
ZA-APA with zero attractor controller selection criterion for sparse system identification,
SIViP(12), No. 2, February 2018, pp. 371-377.
Springer DOI 1802
BibRef

Bergmann, R.[Ronny], Tenbrinck, D.[Daniel],
A Graph Framework for Manifold-Valued Data,
SIIMS(11), No. 1, 2018, pp. 325-360.
DOI Link 1804
BibRef

Sun, C.[Chao], Su, Y.[Yao], Yu, X.G.[Xin-Guo],
Machine Solving on Hypergeometric Distribution Problems,
PSIVTWS17(102-115).
Springer DOI 1806
BibRef

Heravi, A.R., Hodtani, G.A.,
A New Information Theoretic Relation Between Minimum Error Entropy and Maximum Correntropy,
SPLetters(25), No. 7, July 2018, pp. 921-925.
IEEE DOI 1807
entropy, information theory, minimum entropy methods, statistical analysis, MCC, MEE, information theoretic learning, minimum error entropy BibRef

Wang, Z., Lin, J., Wang, Z.,
Hardware-Oriented Compression of Long Short-Term Memory for Efficient Inference,
SPLetters(25), No. 7, July 2018, pp. 984-988.
IEEE DOI 1807
computational complexity, data compression, embedded systems, matrix multiplication, recurrent neural nets, sparse matrices, recurrent neural networks (RNNs) BibRef

Khanna, S.[Saurabh], Murthy, C.R.[Chandra Ramabhadra],
Sparse Recovery From Multiple Measurement Vectors Using Exponentiated Gradient Updates,
SPLetters(25), No. 10, October 2018, pp. 1485-1489.
IEEE DOI 1810
convex programming, iterative methods, sparse matrices, vectors, multiple measurement vector support recovery algorithms, Von Neumann divergence BibRef

Wang, H., Yuan, J.,
Representative Selection on a Hypersphere,
SPLetters(25), No. 11, November 2018, pp. 1660-1664.
IEEE DOI 1811
computational complexity, computational geometry, data analysis, gradient methods, representative examples, pattern discovery, representative selection BibRef

Wang, Y., Tian, Z.,
IVDST: A Fast Algorithm for Atomic Norm Minimization in Line Spectral Estimation,
SPLetters(25), No. 11, November 2018, pp. 1715-1719.
IEEE DOI 1811
compressed sensing, computational complexity, concave programming, convex programming, gradient methods, shrinkage thresholding BibRef

Chen, J.[Jian], He, M.[Minfan], Zeng, T.[Taishan],
A multiscale Galerkin method for second-order boundary value problems of Fredholm integro-differential equation II: Efficient algorithm for the discrete linear system,
JVCIR(58), 2019, pp. 112-118.
Elsevier DOI 1901
Multiscale Galerkin method (MGM), Multilevel augmentation method (MAM), Fredholm integro-differential equation BibRef

Mello, L.H.S.[Lucas Henrique Sousa], Varejão, F.M.[Flávio M.], Rodrigues, A.L.[Alexandre L.], Rauber, T.W.[Thomas W.],
NP-Hardness of minimum expected coverage,
PRL(117), 2019, pp. 45-51.
Elsevier DOI 1901
Complexity, Multi-label learning, Loss minimization, Coverage BibRef

Mazo, L.[Loïc],
Multi-scale Arithmetization of Linear Transformations,
JMIV(61), No. 4, May 2019, pp. 432-442.
Springer DOI 1904
BibRef

Farzmahdi, M.[Mojtaba], Luo, R.[Rong],
Exact window memoization: an optimization method for high-performance image processing,
RealTimeIP(16), No. 2, April 2019, pp. 491-503.
Springer DOI 1904
Efficent computation, using data redundancy to minimize redundant computations. BibRef

Yang, J., Lin, J., Shi, Q., Li, Q.,
An ADMM-Based Approach to Robust Array Pattern Synthesis,
SPLetters(26), No. 6, June 2019, pp. 898-902.
IEEE DOI 1906
array signal processing, convex programming, minimax techniques, ADMM-based approach, bounded-sphere model, alternating direction method of multipliers (ADMM) BibRef

Kushinsky, Y., Maron, H., Dym, N., Lipman, Y.,
Sinkhorn Algorithm for Lifted Assignment Problems,
SIIMS(12), No. 2, 2019, pp. 716-735.
DOI Link 1907
solving linear programs emerging from optimal transport BibRef

Lebrat, L.[Léo], de Gournay, F.[Frédéric], Kahn, J.[Jonas], Weiss, P.[Pierre],
Optimal Transport Approximation of 2-Dimensional Measures,
SIIMS(12), No. 2, 2019, pp. 762-787.
DOI Link 1907
Applications in advanced sampling theory, nonphotorealistic rendering, and path planning. BibRef

Hernandez, M.,
A Comparative Study of Different Variants of Newton-Krylov PDE-Constrained Stokes-LDDMM Parameterized in the Space of Band-Limited Vector Fields,
SIIMS(12), No. 2, 2019, pp. 1038-1070.
DOI Link 1907
BibRef

Debarnot, V.[Valentin], Kahn, J.[Jonas], Weiss, P.[Pierre],
Multiview Attenuation Estimation and Correction,
JMIV(61), No. 6, July 2019, pp. 780-797.
Springer DOI 1907
Used in X-ray or optical tomography and lidar. BibRef

Zhang, H., Wei, X., Wang, R., Meng, F.,
An Efficient Base Conversion Using Variable Length Segmentation and Remainder Transfer,
SPLetters(26), No. 8, August 2019, pp. 1227-1231.
IEEE DOI 1908
digital arithmetic, optimisation, transfer functions, variable length segmentation, conversion overflows, remainder transfer function BibRef

Dytso, A.[Alex], Cardone, M.[Martina], Poor, H.V.[H. Vincent],
On Estimating the Norm of a Gaussian Vector Under Additive White Gaussian Noise,
SPLetters(26), No. 9, September 2019, pp. 1325-1329.
IEEE DOI 1909
AWGN, estimation theory, least mean squares methods, signal processing, vectors, Gaussian vector norm estimation, Gaussian noise BibRef

Abeida, H., Delmas, J.,
Slepian-Bangs Formula and Cramér-Rao Bound for Circular and Non-Circular Complex Elliptical Symmetric Distributions,
SPLetters(26), No. 10, October 2019, pp. 1561-1565.
IEEE DOI 1909
Gaussian distribution, Stochastic processes, Noise measurement, Electronic countermeasures, Closed-form solutions, non-circular complex elliptical symmetric distributions BibRef


Lichtenstein, M.[Moshe], Pai, G.[Gautam], Kimmel, R.[Ron],
Deep Eikonal Solvers,
SSVM19(38-50).
Springer DOI 1909
Deep learning for approximate solutions. BibRef

Deledalle, C.A.[Charles-Alban], Papadakis, N.[Nicolas], Salmon, J.[Joseph], Vaiter, S.[Samuel],
Refitting Solutions Promoted by L12 Sparse Analysis Regularizations with Block Penalties,
SSVM19(131-143).
Springer DOI 1909
BibRef

Hertrich, J.[Johannes], Bacák, M.[Miroslav], Neumayer, S.[Sebastian], Steidl, G.[Gabriele],
Minimal Lipschitz Extensions for Vector-Valued Functions on Finite Graphs,
SSVM19(183-195).
Springer DOI 1909
BibRef

Chung, J.[Julianne], Chung, M.[Matthias], Slagel, J.T.[J. Tanner],
Iterative Sampled Methods for Massive and Separable Nonlinear Inverse Problems,
SSVM19(119-130).
Springer DOI 1909
BibRef

Adilkhanov, A.N., Pavlov, A.V., Taimanov, I.A.,
Discrete Analog of the Jacobi Set for Vector Fields,
CTIC19(1-11).
Springer DOI 1901
BibRef

Wu, B.C.[Bi-Chen], Wan, A.[Alvin], Yue, X.Y.[Xiang-Yu], Jin, P.[Peter], Zhao, S.C.[Si-Cheng], Golmant, N.[Noah], Gholaminejad, A.[Amir], Gonzalez, J.[Joseph], Keutzer, K.[Kurt],
Shift: A Zero FLOP, Zero Parameter Alternative to Spatial Convolutions,
CVPR18(9127-9135)
IEEE DOI 1812
Kernel, Computational modeling, Task analysis, Resource description framework, Aggregates, Standards BibRef

Tourani, S.[Siddharth], Shekhovtsov, A.[Alexander], Rother, C.[Carsten], Savchynskyy, B.[Bogdan],
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models,
ECCV18(II: 264-281).
Springer DOI 1810
Max Product Linear Programming. BibRef

Orlowski, A.[Arkadiusz], Chmielewski, L.J.[Leszek J.],
Ulam Spiral and Prime-Rich Polynomials,
ICCVG18(522-533).
Springer DOI 1810
BibRef

López, M.A.[Marco A.], Marcial-Romero, J.R.[J. Raymundo], De Ita, G.[Guillermo], Moyao, Y.[Yolanda],
A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas,
MCPR18(72-81).
Springer DOI 1807
Satisfiability problem for two Conjunctive Normal Form formulas. BibRef

Wang, W.Q.[Wen-Qi], Aggarwal, V.[Vaneet], Aeron, S.[Shuchin],
Efficient Low Rank Tensor Ring Completion,
ICCV17(5698-5706)
IEEE DOI 1802
tensors, MPS representation: Matrix Product State. TR completion algorithm, alternating minimization algorithm, Tensile stress BibRef

Olsson, C., Carlsson, M., Andersson, F., Larsson, V.,
Non-convex Rank/Sparsity Regularization and Local Minima,
ICCV17(332-340)
IEEE DOI 1802
computational complexity, concave programming, convex programming, gradient methods, matrix algebra, minimisation, TV BibRef

Vogel, C.[Christoph], Pock, T.[Thomas],
A Primal Dual Network for Low-Level Vision Problems,
GCPR17(189-202).
Springer DOI 1711
BibRef

Heiss, T.[Teresa], Wagner, H.[Hubert],
Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images,
CAIP17(I: 397-409).
Springer DOI 1708
Computation using data in sequence, not all at once. BibRef

Dong, S.M.[Shu-Min], Zhuang, X.D.[Xiao-Dong], Yu, J.[Jun], Wang, Y.[Ying], Zhao, B.[Bo],
The design and analysis of adjustment factor in Gerschgorin Criterion for Source Number Estimation,
ICIVC17(823-827)
IEEE DOI 1708
Algorithm design and analysis, Design methodology, Robustness, Signal to noise ratio, adjustment factor, colored noise, gerschgorin disk criterion, source number estimation. BibRef

Chen, C.[Cheng], Yang, C.,
Introducing an in-core hybrid LU implementation on heterogeneous systems,
ICIVC17(1084-1089)
IEEE DOI 1708
Microwave integrated circuits, Niobium, LU factorization, heterogeneous system, in-core BibRef

Wielgus, A., Zarzycki, J.,
Efficient Schur parametrization of near-stationary stochastic processes,
WSSIP17(1-5)
IEEE DOI 1707
Complexity theory, Covariance matrices, DH-HEMTs, Hilbert space, Image processing, Signal processing algorithms, Stochastic processes, Second-order nonstationary stochastic processes, complexity reduction, linear, Schur, parametrization BibRef

Liang, J.W.[Jing-Wei], Fadili, J.M.[Jalal M.], Peyre, G.[Gabriel],
On the convergence rates of proximal splitting algorithms,
ICIP14(4146-4150)
IEEE DOI 1502
Complexity theory BibRef

Arnold, D.G.[D. Gregory], Sturtz, K.[Kirk],
Complexity Analysis of ATR Algorithms Based on Invariants,
CVBVS00(27).
IEEE DOI 0006
BibRef

Zucker, S.W.,
Complexity and Confusion in Computational Vision,
SCIA99(Invited Talk). BibRef 9900

Zucker, S.W.[Steven W.],
Structural Scales in Computational Vision,
AIU96(130-141). BibRef 9600

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Ant Colony Optimization, Bee Colony Optimization .


Last update:Dec 7, 2019 at 17:16:29